On the Restricted Isometry Property of Kronecker-structured Matrices

Abstract

In this work, we study the restricted isometry property (RIP) of Kronecker-structured matrices, formed by the Kronecker product of two factor matrices. Previously, only upper and lower bounds on the restricted isometry constant (RIC) in terms of the RICs of the factor matrices were known. We derive a probabilistic measurement bound for the sth-order RIC. We show that the Kronecker product of two sub-Gaussian matrices satisfies RIP with high probability if the minimum number of rows among two matrices is $\mathcal{O}\left( {s\ln \max \left\{ {{N_1},{N_2}} \right\}} \right)$. Here, s is the sparsity level, and N<inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</inf> and N<inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</inf> are the number of columns in the matrices. We also present improved measurement bounds for the recovery of Kronecker-structured sparse vectors using Kronecker-structured measurement matrices. Finally, our analysis is further extended to the Kronecker product of more than two matrices.