Sparse signal recovery from correlation measurements using the noise collector

The problem of sparse signal recovery from quadratic cross-correlation measurements is considered. Compared to the signal recovery problem that uses linear data, the unknown here is a matrix, X=\rho \rho^{\ast}, formed by the cross correlations of \rho, a K-dimensional vector that is the unknown of the linear problem. Solving for X creates a bottleneck as the number of unknowns grows now quadratically in K. To solve this problem efficiently a dimension reduction approach is proposed in which the contribution of the off-diagonal terms \rho_{i} \rho_{j}^{\ast} for \mathbf{i} \neq \mathbf{j} to the data is treated as noise and is absorbed using the Noise Collector [1]. With this approach, we recover the unknown X by solving a convex linear problem whose cost is similar to the one that uses linear measurements.