Suppose that a solution $widetilde{mathbf{x}}$ to an underdetermined linear system $mathbf{b} = mathbf{A} mathbf{x}$ is given. $widetilde{mathbf{x}}$ is approximately sparse meaning that it has a few large components compared to other small entries.
However, the total number of nonzero components of $widetilde{mathbf{x}}$ is large enough to violate any condition for the uniqueness of the sparsest solution. On the other hand, if only the dominant components are considered, then it will satisfy the uniqueness conditions. One intuitively expects that $widetilde{mathbf{x}}$ should not be far from the true sparse solution $mathbf{x}_0$. We show that this intuition is the case by providing an upper bound on $| widetilde{mathbf{x}} - mathbf{x}_0|$ which is a function of the magnitudes of small components of $widetilde{mathbf{x}}$ but independent from $mathbf{x}_0$. This result is extended to the case that $mathbf{b}$ is perturbed by noise. Additionally, we generalize the upper bounds to the low-rank matrix recovery problem.
We consider the problem of direction-of-arrival (DOA) estimation in unknown partially correlated noise environments where the noise covariance matrix is sparse. A sparse noise covariance matrix is a common model for a sparse array of sensors consiste
d of several widely separated subarrays. Since interelement spacing among sensors in a subarray is small, the noise in the subarray is in general spatially correlated, while, due to large distances between subarrays, the noise between them is uncorrelated. Consequently, the noise covariance matrix of such an array has a block diagonal structure which is indeed sparse. Moreover, in an ordinary nonsparse array, because of small distance between adjacent sensors, there is noise coupling between neighboring sensors, whereas one can assume that nonadjacent sensors have spatially uncorrelated noise which makes again the array noise covariance matrix sparse. Utilizing some recently available tools in low-rank/sparse matrix decomposition, matrix completion, and sparse representation, we propose a novel method which can resolve possibly correlated or even coherent sources in the aforementioned partly correlated noise. In particular, when the sources are uncorrelated, our approach involves solving a second-order cone programming (SOCP), and if they are correlated or coherent, one needs to solve a computationally harder convex program. We demonstrate the effectiveness of the proposed algorithm by numerical simulations and comparison to the Cramer-Rao bound (CRB).
