Sparse solutions to underdetermined Kronecker product systems (Q1039753)

The computation of sparse solutions of an underdetermined system \(A x=b\) with \(m \leq n\) is considered, where \(A\) is given as a Kronecker product or a sum of Kronecker products.The solution is typically non-unique. Thus, the question of the sparsest solution naturally arises, which is the one with minimal non-zero components. Such problems come up in many applications, in particular in optimal signal recovery and in compressed sensing. So far, it has been shown that the sparsest solution can be obtained by using \(l_1\)-minimization via the so-called basis pursuit algorithm. Also, sufficient conditions for this approach are known; these are conditions on the spark, mutual incoherence, or restricted isometry property of the matrix \(A\). Whereas it is possible to determine the mutual incoherence for general matrices, it is difficult to analyze the spark or restricted isometry property. In the present paper, new results on the spark, mutual incoherence,and restricted isometry property are derived if matrix \(A\) is given as a Kronecker product, and on the mutual incoherence if matrix \(A\) is a sum of Kronecker matrices. Especially, conditions are obtained that guarantee to find the sparsest solution by \(l_1\)-minimization.