Many tools from the field of graph signal processing exploit knowledge of the underlying graph's structure (e.g., as encoded in the Laplacian matrix) to process signals on the graph. Therefore, in the case when no graph is available, graph signal processing tools cannot be used anymore. Researchers have proposed approaches to infer a graph topology from observations of signals on its vertices. Since the problem is ill-posed, these approaches make assumptions, such as smoothness of the signals on the graph, or sparsity priors. In this paper, we propose a characterization of the space of valid graphs, in the sense that they can explain stationary signals. To simplify the exposition in this paper, we focus here on the case where signals were i.i.d. at some point back in time and were observed after diffusion on a graph. We show that the set of graphs verifying this assumption has a strong connection with the eigenvectors of the covariance matrix, and forms a convex set. Along with a theoretical study in which these eigenvectors are assumed to be known, we consider the practical case when the observations are noisy, and experimentally observe how fast the set of valid graphs converges to the set obtained when the exact eigenvectors are known, as the number of observations grows. To illustrate how this characterization can be used for graph recovery, we present two methods for selecting a particular point in this set under chosen criteria, namely graph simplicity and sparsity. Additionally, we introduce a measure to evaluate how much a graph is adapted to signals under a stationarity assumption. Finally, we evaluate how state-of-the-art methods relate to this framework through experiments on a dataset of temperatures.

We consider the problem of estimating a deterministic finite alphabet vector f from underdetermined measurements y = A f , where A is a given (random) n × N matrix. Two new convex optimization methods are introduced for the recovery of finite alphabet signals via ℓ ₁ -norm minimization. The first method is based on regularization. In the second approach, the problem is formulated as the recovery of sparse signals after a suitable sparse transform. The regularization-based method is less complex than the transform-based one. When the alphabet size p equals 2 and (n, N) grows proportionally, the conditions under which the signal will be recovered with high probability are the same for the two methods. When p > 2, the behavior of the transform-based method is established. Experimental results support this theoretical result and show that the transform method outperforms the regularization-based one.

In many applications, d-dimensional observations result from the random presence or absence of random signals in independent and additive white Gaussian noise. An estimate of the noise standard deviation can then be very useful to detect or to estimate these signals, especially when standard likelihood theory cannot be applied because of too little prior knowledge about the signal probability distributions. The present paper introduces a new scale estimator of the noise standard deviation when the noisy signals have unknown probability distributions and unknown probabilities of presence less than or equal to one half. The latter assumption can be regarded as to a weak assumption of sparsity. Applied to the detection of noncooperative radio-communications, this new estimator outperforms the standard MAD and its alternatives as well as the trimmed and winsorized robust scale estimators. The Matlab code corresponding to the proposed estimator is available at http://perso.telecom-bretagne.eu/pastor.

This paper addresses the problem of decoding in large-scale multiple-input–multiple-output (MIMO) systems. In this case, the optimal maximum-likelihood (ML) detector becomes impractical due to an exponential increase in the complexity with the signal and the constellation dimensions. This paper introduces an iterative decoding strategy with a tolerable complexity order. We consider a MIMO system with finite constellation and model it as a system with sparse signal sources. We propose an ML relaxed detector that minimizes the Euclidean distance with the received signal while preserving a constant $\ell_{1} $ -norm of the decoded signal. We also show that the detection problem is equivalent to a convex optimization problem, which is solvable in polynomial time. Two applications are proposed, and simulation results illustrate the efficiency of the proposed detector.

This paper addresses the problem of testing whether the Mahalanobis distance between a random signal Θ and a known deterministic model θ₀ exceeds some given non-negative real number or not, when Θ has unknown probability distribution and is observed in additive independent Gaussian noise with positive definite covariance matrix. When Θ is deterministic unknown, we prove the existence of thresholding tests on the Mahalanobis distance to θ₀ that have specified level and maximal constant power (MCP). The MCP property is a new optimality criterion involving Wald's notion of tests with uniformly best constant power ( UBCP) on ellipsoids for testing the mean of a normal distribution. When the signal is random with unknown distribution, constant power maximality extends to maximal constant conditional power (MCCP) and the thresholding tests on the Mahalanobis distance to θ₀ still verify this novel optimality property. Our results apply to the detection of signals in independent and additive Gaussian noise. In particular, for a large class of possible model mismatches, MCCP tests can guarantee a specified false alarm probability, in contrast to standard Neyman-Pearson tests that may not respect this constraint.