In this work, we address the problem of identifying the underlying network structure of data. Different from other approaches, which are mainly based on convex relaxations of an integer problem, here we take a distinct route relying on algebraic properties of a matrix representation of the network. By describing what we call possible ambiguities on the network topology, we proceed to employ sub-modular analysis techniques for retrieving the network support, i.e., network edges. To achieve this we only make use of the network modes derived from the data. Numerical examples showcase the effectiveness of the proposed algorithm in recovering the support of sparse networks.@en

Stationarity is a cornerstone property that facilitates the analysis and processing of random signals in the time domain. Although time-varying signals are abundant in nature, in many contemporary applications the information of interest resides in more irregular domains that can be conveniently represented using a graph. This chapter reviews recent advances in extending the notion of stationarity to random graph signals. This is a challenging task due to the irregularity of the underlying graph domain. To that end, we start by presenting coexisting stationarity definitions along with explanations of their genesis, advantages, and disadvantages. Second, we introduce the concept of power spectral density for graph processes and propose a number of methods for its estimation. These methods include nonparametric approaches such as correlograms and windowed average periodograms as well as parametric approaches. To account for distributed scenarios where the supporting graph is related to an actual network infrastructure, the last part of the chapter discusses how to estimate the power spectral density of a graph process when having access to only a subset of the nodes. To gain intuition and insights, the concepts and schemes presented throughout the chapter are illustrated with a running example based on a real-world social graph.@en

In today's society, we are flooded with massive volumes of data in the order of a billion gigabytes on a daily basis from pervasive sensors. It is becoming increasingly challenging to locally store and transport the acquired data to a central location for signal/data processing (i.e., for inference). To alleviate these problems, it is evident that there is an urgent need to significantly reduce the sensing cost (i.e., the number of expensive sensors) as well as the related memory and bandwidth requirements by developing unconventional sensing mechanisms to extract as much information as possible yet collecting fewer data. The first aim of this thesis is to develop theory and algorithms for data reduction. We develop a data reduction tool called sparse sensing, which consists of a deterministic and structured sensing function (guided by a sparse vector) that is optimally designed to achieve a desired inference performance with the reduced number of data samples. The first part of this thesis is dedicated to the development of sparse sensing mechanisms and convex programs to efficiently design sparse sensing functions. We design sparse sensing functions under the assumption that the data is not yet available and the model information is perfectly known. Sparse sensing offers a number of advantages over compressed sensing (a state-of-the-art data reduction method for sparse signal recovery). One of the major differences is that in sparse sensing the underlying signals need not be sparse. This allows us to consider general signal processing tasks (not just sparse signal recovery) under the proposed sparse sensing framework. Specifically, we focus on fundamental statistical inference tasks, like estimation, filtering, and detection. In essence, we present topics that transform classical (e.g., random or uniform) sensing methods to low-cost data acquisition mechanisms tailored for specific inference tasks. The developed framework can be applied to sensor selection, sensor placement, or sensor scheduling, for example. In the second part of this thesis, we focus on some applications related to distributed sampling using sensor networks. Sensor networks can be used as a spatial sampling device, that is, to faithfully represent distributed signals (e.g., a spatially varying phenomenon such as a temperature field). On top of that, the distributed signals can exist in space and time, where the temporal sampling is achieved using analog-to-digital converters, for example. Each sensor has an independent sample clock, and its stability essentially determines the alignment of the temporal sampling grid across the sensors. Due to imperfections in the oscillator, the sample clocks drift from each other, resulting in the misalignment of the temporal sampling grids. To overcome this issue, we devise a mechanism to distribute the sample clock wirelessly. Specifically, we perform wireless clock synchronization based on the time-of-flight measurements of broadcast messages. In addition, clock synchronization also plays a central role in other time-based sensor network applications such as localization. Localization is increasingly gaining popularity in many applications, especially for monitoring environments beyond human reach, e.g., using robots or drones with several sensor units mounted on it. Consequently we now have to localize more than one sensor or even localize the whole sensing platform. Therefore, we extend the classical localization paradigm to localize a (rigid) sensing platform by exploiting the knowledge of the sensor placement on the platform. In particular, we develop algorithms for rigid body localization, i.e., for estimating the position and orientation of the rigid platform using distance measurements. Given the central role of sensing and sensor networks, the results presented in this thesis impacts a wide range of applications.@en

In this paper the focus is on sampling and reconstruction of signals supported on nodes of arbitrary graphs or arbitrary signals that may be represented using graphs, where we extend concepts from generalized sampling theory to the graph setting. To recover such signals from a given set of samples, we develop algorithms that incorporate prior knowledge on the original signal when available such as smoothness or subspace priors related to the underlying graph. For reconstructing arbitrary signals, we constrain the reconstruction to the graph, and provide a consistent reconstruction method, in which both the reconstructed signal and the input yield exactly the same measurements. Given a set of graph frequency domain samples, the sampling and interpolation operations may be efficiently implemented using linear shift-invariant graph filters.@en

Orthogonal signal-division multiplexing (OSDM) is a promising modulation scheme that provides a generalized framework to unify orthogonal frequency-division multiplexing (OFDM) and single-carrier frequency-domain equalization. By partitioning each data block into vectors, it allows for a flexible configuration to trade off resource management flexibility with peak-to-average power ratio. In this paper, an OSDM system is proposed for underwater acoustic communications. The channel Doppler effect after front-end resampling is modeled as a common time-varying phase on all propagation paths. It leads to a special signal distortion structure in the OSDM system, namely, intervector interference, which is analogous to the intercarrier interference in the conventional OFDM system. To counteract the related performance degradation, the OSDM receiver performs iterative detection, integrating joint channel impulse response and phase estimation, equalization, and decoding in a loop. Meanwhile, to avoid inversion of large matrices in channel equalization, frequency-domain per-vector equalization is designed, which can significantly reduce the computational complexity. Furthermore, the performance of the proposed OSDM system is evaluated through both numerical simulations and a field experiment, and its reliability over underwater acoustic channels is confirmed.@en

Multiple-input multiple-output (MIMO) radar is known for its superiority over conventional radar due to its antenna and waveform diversity. Although higher angular resolution, improved parameter identifiability, and better target detection are achieved, the hardware costs (due to multiple transmitters and multiple receivers) and high-energy consumption (multiple pulses) limit the usage of MIMO radars in large scale networks. On one hand, higher angle and velocity estimation accuracy is required, but on the other hand, a lower number of antennas/pulses is desirable. To achieve such a compromise, in this paper, the Cramér-Rao lower bound (CRLB) for the angle and velocity estimator is employed as a performance metric to design the antenna and the pulse placement. It is shown that the CRLB derived for two targets is a more appropriate criterion in comparison with the single-target CRLB since the two-target CRLB takes into account both the mainlobe width and the sidelobe level of the ambiguity function. In this paper, several algorithms for antenna and pulse selection based on convex and submodular optimization are proposed. Numerical experiments are provided to illustrate the developed theory.@en

In this paper, we present a calibration algorithm for acoustic vector sensors arranged in a uniform linear array configuration. To do so, we do not use a calibrator source, instead we leverage the Toeplitz blocks present in the data covariance matrix. We develop linear estimators for estimating sensor gains and phases. Further, we discuss the differences of the presented blind calibration approach for acoustic vector sensor arrays in comparison with the approach for acoustic pressure sensor arrays. In order to validate the proposed blind calibration algorithm, simulation results for direction-of-arrival (DOA) estimation with an uncalibrated and calibrated uniform linear array based on minimum variance distortion less response and multiple signal classification algorithms are presented. The calibration performance is analyzed using the Cramér-Rao lower bound of the DOA estimates.@en

An analytical algebraic approach for distributed network identification is presented in this paper. The information propagation in the network is modeled using a state-space representation. Using the observations recorded at a single node and a known excitation signal, we present algorithms to compute the eigenfrequencies and eigenmodes of the graph in a distributed manner. The eigenfrequencies of the graph may be computed using a generalized eigenvalue algorithm, while the eigenmodes can be computed using an eigenvalue decomposition. The developed theory is demonstrated using numerical experiments.@en

In this paper, we consider the problem of subsampling and reconstruction of signals that reside on the vertices of a product graph, such as sensor network time series, genomic signals, or product ratings in a social network. Specifically, we leverage the product structure of the underlying domain and sample nodes from the graph factors. The proposed scheme is particularly useful for processing signals on large-scale product graphs. The sampling sets are designed using a low-complexity greedy algorithm and can be proven to be near-optimal. To illustrate the developed theory, numerical experiments based on real datasets are provided for sampling 3D dynamic point clouds and for active learning in recommender systems.@en

Detection of a signal under noise is a classical signal processing problem. When monitoring spatial phenomena under a fixed budget, i.e., either physical, economical or computational constraints, the selection of a subset of available sensors, referred to as sparse sensing, that meets both the budget and performance requirements is highly desirable. Unfortunately, the subset selection problem for detection under dependent observations is combinatorial in nature and suboptimal subset selection algorithms must be employed. In this work, different from the widely used convex relaxation of the problem, we leverage submodularity, the diminishing returns property, to provide practical near-optimal algorithms suitable for large-scale subset selection. This is achieved by means of low-complexity greedy algorithms, which incur a reduced computational complexity compared to their convex counterparts.@en

We consider the problem of designing sparse sampling strategies for multidomain signals, which can be represented using tensors that admit a known multilinear decomposition. We leverage the multidomain structure of tensor signals and propose to acquire samples using a Kronecker-structured sensing function, thereby circumventing the curse of dimensionality. For designing such sensing functions, we develop low-complexity greedy algorithms based on submodular optimization methods to compute near-optimal sampling sets. We present several numerical examples, ranging from multiantenna communications to graph signal processing, to validate the developed theory.@en

In this paper we focus on the relative position and orientation estimation between rigid bodies in an anchorless scenario. Several sensor units are installed on the rigid platforms, and the sensor placement on the rigid bodies is known beforehand (i.e., relative locations of the sensors on the rigid body are known). However, the absolute position of the rigid bodies is not known. We show that the relative localization of rigid bodies amounts to the estimation of a rotation matrix and the relative distance between the centroids of the rigid bodies. We measure all the unknown pairwise distances between the sensors, which we use in a constrained least squares estimator. Furthermore, we also allow missing links between the sensors. The simulations support the developed theory.@en

In this paper, we propose sensor selection strategies, based on convex and greedy approaches, for designing sparse samplers for composite detection. Particularly, we focus our attention on sparse samplers for matched subspace detectors. Differently from previous works, that mostly rely on random matrices to perform compression of the sub-spaces, we show how deterministic samplers can be designed under a Neyman-Pearson-like setting when the generalized likelihood ratio test is used. For a less stringent case than the worst case design, we introduce a submodular cost that obtains comparable results with its convex counterpart, while having a linear time heuristic for its near optimal maximization.@en

In this work, we introduce subset selection strategies for signal reconstruction based on kernel methods, particularly for the case of kernel-ridge regression. Typically, these methods are employed for exploiting known prior information about the structure of the signal of interest. We use the mean squared error and a scalar function of the covariance matrix of the kernel regressors to establish metrics for the subset selection problem. Despite the NP-hard nature of the problem, we introduce efficient algorithms for finding approximate solutions for the proposed metrics. Finally, numerical experiments demonstrate the applicability of the proposed strategies.@en

We study the sensor selection problem for field estimation, where a best subset of sensors is activated to monitor a spatially correlated random field. Different from most commonly used centralized selection algorithms, we propose a decentralized architecture where sensor selection can be carried out in a distributed way and by the sensors themselves. A decentralized approach is essential since each sensor has access only to the information (e.g., correlation) in its neighborhood. To make distributed optimization possible, we decompose the global cost function into local cost functions that require only the information in local neighborhoods of sensors. We then employ the alternating direction method of multipliers (ADMM) to solve the proposed sensor selection problem. In our algorithm, each sensor solves small-scale optimization problems, and communicates directly only with its immediate neighbors. Numerical results are provided to show the effectiveness of our approach.@en

We study the sensor selection problem for field estimation, where a best subset of sensors is activated to monitor a spatially correlated random field. Different from most commonly used centralized selection algorithms, we propose a decentralized architecture where sensor selection can be carried out in a distributed way and by the sensors themselves. A decentralized approach is essential since each sensor has access only to the information (e.g., correlation) in its neighborhood. To make distributed optimization possible, we decompose the global cost function into local cost functions that require only the information in local neighborhoods of sensors. We then employ the alternating direction method of multipliers (ADMM) to solve the proposed sensor selection problem. In our algorithm, each sensor solves small-scale optimization problems, and communicates directly only with its immediate neighbors. Numerical results are provided to show the effectiveness of our approach.@en

In this paper, we present a greedy sensor selection algorithm for minimum variance distortionless response (MVDR) beamforming under a modular budget constraint. In particular, we propose a submodular set-function that can be maximized using a linear-time greedy heuristic that is near optimal. Different from the convex formulation that is typically used to solve the sensor selection problem, the method in this paper neither involves computationally intensive semidefinite programs nor convex relaxation of the Boolean variables. While numerical experiments show a comparable performance between the convex and submodular relaxations, in terms of output signal-to-noise ratio, the latter finds a near-optimal solution with a significantly reduced computational complexity.@en

In this paper, we present a greedy sensor selection algorithm for minimum variance distortionless response (MVDR) beamforming under a modular budget constraint. In particular, we propose a submodular set-function that can be maximized using a linear-time greedy heuristic that is near optimal. Different from the convex formulation that is typically used to solve the sensor selection problem, the method in this paper neither involves computationally intensive semidefinite programs nor convex relaxation of the Boolean variables. While numerical experiments show a comparable performance between the convex and submodular relaxations, in terms of output signal-to-noise ratio, the latter finds a near-optimal solution with a significantly reduced computational complexity.@en

In this paper, we are interested in learning the underlying graph structure behind training data. Solving this basic problem is essential to carry out any graph signal processing or machine learning task. To realize this, we assume that the data is smooth with respect to the graph topology, and we parameterize the graph topology using an edge sampling function. That is, the graph Laplacian is expressed in terms of a sparse edge selection vector, which provides an explicit handle to control the sparsity level of the graph. We solve the sparse graph learning problem given some training data in both the noiseless and noisy settings. Given the true smooth data, the posed sparse graph learning problem can be solved optimally and is based on simple rank ordering. Given the noisy data, we show that the joint sparse graph learning and denoising problem can be simplified to designing only the sparse edge selection vector, which can be solved using convex optimization.@en