Block-sparse Recovery of Semidefinite Systems and Generalized Null Space Conditions

2019/07/22 by Heuer, Janin, Matter, Frederic, Pfetsch, Marc E. +1
#90C22 #94A12 #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.1907.09442

Abstract

This article considers the recovery of low-rank matrices via a convex nuclear-norm minimization problem and presents two null space properties (NSP) which characterize uniform recovery for the case of block-diagonal matrices and block-diagonal positive semidefinite matrices. These null-space conditions turn out to be special cases of a new general setup, which allows to derive the mentioned NSPs and well-known NSPs from the literature. We discuss the relative strength of these conditions and also present a deterministic class of matrices that satisfies the block-diagonal semidefinite NSP.

Related

• Necessary and Sufficient Null Space Condition for Nuclear Norm Minimization in Low-Rank Matrix Recovery
• New Null Space Results and Recovery Thresholds for Matrix Rank Minimization
• Low-rank matrix recovery via regularized nuclear norm minimization
• A Simplified Approach to Recovery Conditions for Low Rank Matrices
• An Optimal Condition of Robust Low-rank Matrices Recovery