Optimal RIP Constants In Compressed Sensing

Compressed sensing has become a very important research field in applied mathematics. It includes functional approximation theory, statistical theory, matrix theory, and optimization theory etc. In particular, due to its successful application in MRI, and urgent demands in big data science,the research in this field is more and more important.Restricted isometry constant (RIP) is the key concept in compressed sensing. And we can use the upper bound of the RIP constant to transfer a combinatorial problem to a convex optimization problem. In 2005, E. J. Candes and T. Tao used the RIP constant to describe their equivalence.This work has attracted many scholars close attention (one hour's talk and 45 minutes' talk at the ICM in 2006). However, as the Candes and Tao's paper pointed out that,this bound is not optimal.They suggested that we can improve this bound by introducing more elegant analysis skills. By far, large mount of work has focused on the estimation of the upper bound. We need to point out that Candes proved that when ?2k < (?)- 1, we can recover the k-sparse signal exactly via solving the l1-minimization model. After that, Tony Cai and Anru Zhang proved that when 4/3 < t,(?) is the optimal RIP bounds. Besides, they conjectured that when 0 < t < 4/3,the optimal bounds are ?tk <t/(4-t). In chapter 2, we have proved the conjecture and furthermore,the similar results can be applied in low rank matrix recovery. So far, combined with[5], all the RIP constants ?tk have been solved when t > 0. We also discuss the noisy cases and approximately sparse cases. To solve the conjecture, we make use of the sparse representation of convex polytope,and combinatorial methods, such that RIP of tk-order can be perfectly applied.In chapter 3, we also consider the unified analysis of RIP bounds via lp minimization to recover the sparse signals. This is also the focus in lp minimization. By far,a large mount of paper try to improve the bounds. However, there are no optimal upper bounds. Here, we finally give the unified optimal upper bounds. We prove that if the measurement matrix A satisfies the RIP condition ?2k < ?(p), then all k-sparse signals x can be exactly recovered via the constrained lp minimization. Furthermore, we prove that for all ? > 0, the condition ?2k < ?p+? cannot guarantee the recovery of all the k-sparse signals. This result can also be applied to low rank matrix recovery.In particular, when p=1, the corresponding result (?) is proved in pape[5].In practical fields, many signals are not sparse in the representation of orthonormal base,but are sparse in the representation of redundant dictionaries. For instance, they are sparse in the representation of tight frames. The conception of D-RIP is the key in the analysis of such problems.In chapter 4, we focus on the signal recovery under the tight frame. And as an application, we also solve the optimal D-RIP upper bounds under the tight frame.