- New Bounds for Restricted Isometry Constants in Low-rank Matrix Recovery Lingchen Kong(konglchen126.com) Naihua Xiu(nhxiubjtu.edu.cn) Abstract: In this paper, we establish new bounds for restricted isometry constants (RIC) in low-rank matrix recovery. Let $\A$ be a linear transformation from $\R^{m \times n}$ into $\R^p$, and $r$ the rank of recovered matrix $X\in \R^{m \times n}$. Our main result is that if the condition on RIC satisfies $\delta_{2r+k}+2(\frac{r}{k})^{1/2}\delta_{\max\{r+\frac{3}{2}k,2k\}}<1$ for a given positive integer $k\leq m-r$, then $r$-rank matrix can be exactly recovered via nuclear norm minimization problem in noiseless case, and estimated stably in the noise case. Taking different $k$, we obtain some improved and new RIC bounds such as $\delta_{\frac{7}{3} r}+2\sqrt{3}\delta_{1.5r}<1$, $\delta_{2.5r}+2\sqrt{2}\delta_{1.75r}<1$, $\delta_{2r+1}+2\sqrt{r}\delta_{r+2}<1$, $\delta_{2r+2}+\sqrt{2r}\delta_{r+3}<1$, or $\delta_{2r+4}+\sqrt{r}\delta_{r+7}<1$. To the best of our knowledge, these are the first such conditions on RIC. Keywords: low-rank matrix recovery, restricted isometry constant, bound, nuclear norm minimization. Category 1: Combinatorial Optimization Category 2: Convex and Nonsmooth Optimization (Convex Optimization ) Citation: Beijing Jiaotong University, January, 2011) Download: [PDF]Entry Submitted: 01/25/2011Entry Accepted: 01/25/2011Entry Last Modified: 01/25/2011Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Programming Society.