S-semigoodness for Low-Rank Semidefinite Matrix Recovery

Lingchen Kong(konglchen126.com)
Jie Sun(jsunnus.edu.sg)
Naihua Xiu(nhxiubjtu.edu.cn)

Abstract: We extend and characterize the concept of $s$-semigoodness for a sensing matrix in sparse nonnegative recovery (proposed by Juditsky , Karzan and Nemirovski [Math Program, 2011]) to the linear transformations in low-rank semidefinite matrix recovery. We show that s-semigoodness is not only a necessary and sufficient condition for exact $s$-rank semidefinite matrix recovery by a semidefinite program, but also provides a stable recovery under some conditions. We also show that both s-semigoodness and semiNSP are equivalent.

Keywords: low-rank semidefinite matrix recovery, unitary property, necessary and sufficient condition, $s$-semigoodness, exact and stable recovery

Category 1: Convex and Nonsmooth Optimization (Convex Optimization )

Category 2: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Citation: Department of Applied Mathematics, Beijing Jiaotong University, Research Report, 2013

Download: [PDF]

Entry Submitted: 01/18/2013
Entry Accepted: 01/18/2013
Entry Last Modified: 01/18/2013

Modify/Update this entry