Abstract and Applied Analysis
Volume 2013 (2013), Article ID 101974, 9 pages
http://dx.doi.org/10.1155/2013/101974
Research Article

-Goodness for Low-Rank Matrix Recovery

Lingchen Kong,1 Levent Tunçel,2 and Naihua Xiu1

1Department of Applied Mathematics, Beijing Jiaotong University, Beijing 100044, China
2Department of Combinatorics and Optimization, Faculty of Mathematics, University of Waterloo, Waterloo, ON, Canada N2L 3G1

Received 21 January 2013; Accepted 17 March 2013

Academic Editor: Jein-Shan Chen

Copyright © 2013 Lingchen Kong et al. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

Abstract

Low-rank matrix recovery (LMR) is a rank minimization problem subject to linear equality constraints, and it arises in many fields such as signal and image processing, statistics, computer vision, and system identification and control. This class of optimization problems is generally hard. A popular approach replaces the rank function with the nuclear norm of the matrix variable. In this paper, we extend and characterize the concept of -goodness for a sensing matrix in sparse signal recovery (proposed by Juditsky and Nemirovski (Math Program, 2011)) to linear transformations in LMR. Using the two characteristic -goodness constants, and , of a linear transformation, we derive necessary and sufficient conditions for a linear transformation to be -good. Moreover, we establish the equivalence of -goodness and the null space properties. Therefore, -goodness is a necessary and sufficient condition for exact -rank matrix recovery via the nuclear norm minimization.