Back to Search
Start Over
A Proof of Conjecture on Restricted Isometry Property Constants \delta tk\ \left(0<t<\frac {4}{3}\right).
- Source :
- IEEE Transactions on Information Theory; Mar2018, Vol. 64 Issue 3, p1699-1705, 7p
- Publication Year :
- 2018
-
Abstract
- In this paper, we give a complete answer to the conjecture on restricted isometry property (RIP) constants \delta tk (0<t<({4}/{3})) , which was proposed by T. Cai and A. Zhang. We have shown that when 0 < t < (4/3) , the condition \delta _{tk}<({t}/({4-t})) is sufficient to guarantee the exact recovery for all k -sparse signals in the noiseless case via the constrained \ell 1 -norm minimization. These bounds are sharp in the sense that for any \epsilon >0,\,\,\delta tk<({t}/({4-t}))+\epsilon 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 \delta _{tk} for all t > 0$ is obtained to guarantee the exact recovery of all k$ -sparse signals and matrices with rank at most k$ by -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. [ABSTRACT FROM PUBLISHER]
Details
- Language :
- English
- ISSN :
- 00189448
- Volume :
- 64
- Issue :
- 3
- Database :
- Complementary Index
- Journal :
- IEEE Transactions on Information Theory
- Publication Type :
- Academic Journal
- Accession number :
- 128115215
- Full Text :
- https://doi.org/10.1109/TIT.2017.2705741