I am working on sparse matrices. I need a structured sensing matrix other than reed Solomon,BCH,LPDC,sparse circulant matrix ,Kronecker product,Toeplitz sensing matrix. any other new findings of family of measurement matrix?
For deterministically constructed matrices with n rows the best RIP results that can be obtained with current proof techniques are O(\sqrt n). This is not nearly as good as the n/log(n) type results which can be obtained with random matrices.
For results and analysis of one deterministic construction, you might like to look at my papers on compressed sensing, available from my page.
In fact, there is a deterministic construction with n rows having RIP-constants small for O(n^(1/(2+\epsilon)) for a very small but still positive epsilon, due to Bourgain et al. Dustin Mixon has written a blog entry on this topic: https://dustingmixon.wordpress.com/2013/12/02/deterministic-rip-matrices-breaking-the-square-root-bottleneck/.
When using random matrices, is there an unfortunate possibility to encounter an almost singular column submatrix with n\log n columns?
Recall that Murphy's law states: "If anything can go wrong, it will."
@Axel - the construction of Bourgain et al. is deterministic and is an amazing theoretical breakthrough. Unfortunately it relies on results from additive combinatorics which require the size of the matrices constructed to be too large to fit on a computer.
@I. E. Karporin - In the original work of Candes-Romberg-Tao they show that in a random ensemble there is a very high probability that EVERY column column sub matrix with n/log n columns is close to an isometry. So the probability of writing down a truly random matrix with the property you describe is exponentially small.
- Badges
- Science topic
- Similar topics
- Mathematics
- Algebra
- Matrix