Performance guarantees for Schatten-p quasi-norm minimization in recovery of low-rank matrices

• Recovery of low-rank matrices from compressed linear measurements is considered.
• Schatten-p quasi-norm minimization is one of the solutions for the above problem.
• We address theoretical guarantees for this approach.
• First, we provide a sufficient condition for exact recovery.
• Second, some conditions for robust and stable recovery are provided.

We address some theoretical guarantees for Schatten-p   quasi-norm minimization (p∈(0,1]p∈(0,1]) in recovering low-rank matrices from compressed linear measurements. Firstly, using null space properties of the measurement operator, we provide a sufficient condition for exact recovery of low-rank matrices. This condition guarantees unique recovery of matrices of ranks equal or larger than what is guaranteed by nuclear norm minimization. Secondly, this sufficient condition leads to a theorem proving that all restricted isometry property (RIP) based sufficient conditions for ℓpℓp quasi-norm minimization generalize to Schatten-p quasi-norm minimization. Based on this theorem, we provide a few RIP-based recovery conditions.