* This article is only a review for my personal use. There may have some mistakes. Please do not trust in this article.
* If you noticed any mistakes in this article, please notify me. Thanks a lot.
In the following description, M is the number of measurements needed, N is the length of signal, K is sparsity, Φ is measurement matrix, Ψ is sparse basis. C is a constant.
Y = AX = \Phi\Psi X
The requirement for M
[1] Sparsity and Incoherence in compressive sampling
M \geq C \cdot \mu^2(\Phi, \Psi) \cdot K {\text log}N
[2] An introduction to Compressive Sampling
Form A obeying RIP i)-iv)
M = O(K {\text log}(N/K))
M \geq C \cdot K {\text log}(N/K)
i)-iii) see
[3] A simple proof of the restricted isometry property for random matrices
iv) see
[4] Uniform uncertainty principles for Bernoulli and sub-gaussian ensembles
Form A by first finding paris of incoherent orthobases \Phi, \Psi, and then exracting M coordinates uniformly at random using R: A = R\Phi\Psi.
M \geq C \cdot ({\text log}N)^4
M \geq C \cdot ({\text log}N)^5 for a lower probability of failure
see [6] and [7] On sparse reconstruction from Fourier and Gaussian measurements
[6] Near-optimal signal recovery from random projections and universal encoding strategies
[8] Compressed Sensing, D.L.Donoho
[9] Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
[10] Neighborliness of randomly projected simplices in high dimensions
[11] High-dimensional centrally symmetreic polytopes with neighborliness proportional to dimension
M = O(K {\text log}(N))
M \geq C \cdot K \cdot {\text log}N
[12] Compressive Sensing, R.G.Baranuik
M \geq C \cdot K {\text log}(N/K)
it cited the result from [8] and [9]. Are they the same?
To summary, there are 4 expressions:
1)
M = O(K {\text log}(N))
M \geq C \cdot K \cdot {\text log}N
2)
M \geq C \cdot K {\text log}(N/K)
3)
M \geq C \cdot ({\text log}N)^4
M \geq C \cdot ({\text log}N)^5
4)
M \geq C \cdot \mu^2(\Phi, \Psi) \cdot K {\text log}N
1) and 2) are quite similar with each other; 1) is noisy situation and 2) is noiseless.
4) is quite similar with 1), except the parameter \mu^2(\Phi, \Psi), which is a measure for the incoherence between the two matrix.
No comments:
Post a Comment