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.
Citation
Beijing Jiaotong University, January, 2011)
Article
View New Bounds for Restricted Isometry Constants in Low-rank Matrix Recovery