  


New Bounds for Restricted Isometry Constants in Lowrank Matrix Recovery
Lingchen Kong(konglchen126.com) Abstract: In this paper, we establish new bounds for restricted isometry constants (RIC) in lowrank 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 mr$, 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: lowrank 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/2011 Modify/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  