A Proof of Conjecture on Restricted Isometry Property Constants $\delta _{tk}\ \left(0<t<\frac {4}{3}\right)$

Song Li

IEEE Transactions on Information Theory · 2017 · 75 citations · 20 references

Concepts

Abstract

In this paper, we give a complete answer to the conjecture on restricted isometry property (RIP) constants &#x03B4;<sub>tk</sub>(0&lt;;t&lt;;(4/3)), which was proposed by T. Cai and A. Zhang. We have shown that when 0 &lt;; t &lt;; (4/3), the condition &#x03B4;<sub>tk</sub> &lt;; (t/(4-t)) is sufficient to guarantee the exact recovery for all k-sparse signals in the noiseless case via the constrained &#x2113;<sub>1</sub>-norm minimization. These bounds are sharp in the sense that for any &#x03F5;&gt;0, &#x03B4;<sub>tk</sub> &lt;; (t/(4-t)) + &#x03F5; cannot guarantee the exact recovery of some k-sparse signals. Furthermore, it will be shown that similar characterizations also hold for low-rank matrix recovery. Thus, combined with T. Cai and A. Zhang's work, a complete characterization for sharp RIP constants &#x03B4;<sub>tk</sub> for all t &gt; 0 is obtained to guarantee the exact recovery of all k-sparse signals and matrices with rank at most k by &#x2113;<sub>1</sub>-norm minimization and nuclear norm minimization, respectively. Noisy cases and approximately sparse cases are also considered. To solve the conjecture, we construct a few identities so that RIP of order tk, which is the target of our main results, can be perfectly applied to them.

References

20