This paper concerns solving the sparse deconvolution and demixing problem using l1,2-minimization. We show that under a certain structured random model, robust and stable recovery is possible. The results extend results of Ling and Strohmer (Inverse Probl. 31, 115002 2015), and in particular theoretically explain certain experimental findings from that paper. Our results do not only apply to the deconvolution and demixing problem, but to recovery of column-sparse matrices in general.
As observant readers already may have pointed out, the ''true dimension'' of the problem of recovering a matrix @math with @math and @math @math -sparse is neither @math nor @math , but instead @math (a mathematically precise statement of this claim is provided in (Kech and Krahmer 2016 @cite_14 )). As of today, to the best knowledge of the author, there are no convex minimization procedures which succeed which such few measurements. In this context, ( Bresler, Lee and Wu 2013 @cite_8 ) should be mentioned. In that paper, the authors describe a alternating minimization procedure which under some additional conditions on the vectors @math and @math succeed with high probability already when @math is of the order of @math .
@cite_14 @cite_8
2302736609 1600586145
We study identifiability for bilinear inverse problems under sparsity and subspace constraints. We show that, up to a global scaling ambiguity, almost all such maps are injective on the set of pairs of sparse vectors if the number of measurements @math exceeds @math , where @math and @math denote the sparsity of the two input vectors, and injective on the set of pairs of vectors lying in known subspaces of dimensions @math and @math if @math . We also prove that both these bounds are tight in the sense that one cannot have injectivity for a smaller number of measurements. Our proof technique draws from algebraic geometry. As an application we derive optimal identifiability conditions for the deconvolution problem, thus improving on recent work of [1]. Compressed sensing of simultaneously sparse and rank-one matrices enables recovery of sparse signals from a few linear measurements of their bilinear form. One important question is how many measurements are needed for a stable reconstruction in the presence of measurement noise. Unlike the conventional compressed sensing for sparse vectors, where convex relaxation via the @math -norm achieves near optimal performance, for compressed sensing of sparse and rank-one matrices, recently it has been shown by that convex programmings using the nuclear norm and the mixed norm are highly suboptimal even in the noise-free scenario. We propose an alternating minimization algorithm called sparse power factorization (SPF) for compressed sensing of sparse rank-one matrices. Starting from a particular initialization, SPF achieves stable recovery and requires number of measurements within a logarithmic factor of the information-theoretic fundamental limit. For fast-decaying sparse signals, SPF starting from an initialization with low computational cost also achieves stable reconstruction with the same number of measurements. Numerical results show that SPF empirically outperforms the best known combinations of mixed norm and nuclear norm.