A reader sent me the following:Dear Igor,I always read your blog and now I have a doubt about RIP. Suppose matrix A satisfy RIP, that is the singular values are bounded above and below by 1-\delta and 1+delta. Now if we set A’=cA, where c is a constant, then the singular values are bounded above and below by c^2(1-\delta) and c^2(1-\delta). Thus A and A’ have different \delta. A’ may be not satisfy RIP. But for signal reconstruction, A and A’ are no different. So how do you explain it? Or for a given matrix B, how can we choose a constant c, make matrix cB have the minimum \delta? Do you have any suggestions?....
My answer:
You are absolutely right. I think it was mentioned in the blog before and this is is why I keep on telling people who are interested in checking recoverability to not rely too much on the RIP in the first place.
Maybe I should compile a list of the different entries on RIP instead of just relying on a word search. Items relevant to the RIP subject include:
- CS: Finding the Restricted Isometry Constant, Part Three
- CS: Finding the Restricted isometry Constant, Part Deux.
- CS: Finding the Restricted Isometry Constant, Random SVD, ART in CTs ?, Patents, Cheap CS Sensing ?
- CS: Food for thoughts for the week-end.
- CS: RIP vs NSP, Clarifications by Jared Tanner and Remi Gribonval.
- CS: RIP vs NSP, Deterministic Sensing Matrices with Statistical Isometry Property , Modified Basis Pursuit Denoising,
- CS: ISD, A New Compressed Sensing Algorithm via Iterative Support Detection (and NSP vs RIP)
- CS: Restricted Isometry Property, What Is It Good For ?
I could also include the LinkedIn discussions on the subject ?
Around the blogs, here some entries somehow related to compressive sensing:
Dick Lipton
Djalil Chafai
Bob Sturm
- Paper of the Day (Po'D): Experiments in Audio Similarity Edition
- Bringing Music to the Masses Does Not Mean Bringing Intelligence to Music
- Paper of the Day (Po'D): Consensus matching pursuit for multi-trial EEG signals Edition
Gonzalo Vazquez-vilar
Laurent Duval
Hong Noh let me know of the following meeting:
INSPIRE 2010
Conference on information representation and estimation
University College London, London, UK.
September 6-8, 2010Abstract:Mathematical methods for signal processing and in general for data representation and inference are growing more and more sophisticated. Successful applications of such methods range from medical imaging to security. Developments in mathematics and signal processing are however often divergent. Therefore, the main aim of this conference is to bring together signal processing researchers with statisticians and mathematicians working on problems related to data modelling and estimation, to encourage the exchange of ideas as well as to discuss theoretical underpinning of the methods and domains of application.The INSPIRE 2010 conference will be held at the Anatomy JZ Young LT at University College London from September 6 till September 8, 2010. So please, book these dates!The conference includes two plenary talks and a few focused sessions. The plenary speakers are Prof. V. Goyal from Massachusetts Institute of Technology (MIT) and Prof. K Oweiss from Michigan State University. The focused sessions this year are on topics related to sparse inference, overcomplete representations and frames, climate and inference, signal processing in neuroscience, and machine learning.There will also be contributed session and posters. The contributed papers and posters are solicited in any area related to data representation and inference, but contributions covering the specific topics of the focused sessions are particularly welcome. We invite you to submit two-page extended abstracts, with pointers to reference material where appropriate. Submissions should be sent to p.dragottiATimperial.acDOTuk and should be received by June 15th 2010. Notification of acceptance will be given by July 10th 2010. Finally, there is going to be a tutorial session on methods of analysis in compressed sensing. Instructor: Dr Jared Tanner, Edinburgh UniversityPlease notice that registration is free and includes lunches and coffee-breaks for the duration of the conference. Those contributing a paper or a poster will have the accommodation provided for the whole duration of the conference.
Thanks Hong.
Credit: JAXA / JSPEC
Waiting for a signal from Hayabusa. A directional antenna sits in the Woomera desert in southern Australia on June 10, 2010, waiting to hear a signal from the incoming Hayabusa sample return capsule.
1 comment:
"... Now if we set A’=cA, where c is a constant, then the singular values are bounded above and below by c^2(1-\delta) and c^2(1-\delta). Thus A and A’ have different \delta. A’ may be not satisfy RIP. But for signal reconstruction, A and A’ are no different. So how do you explain it? Or for a given matrix B, how can we choose a constant c, make matrix cB have the minimum \delta? Do you have any suggestions?...."
Multiplication by a constant is not a problem. what matters actually is the ratio of the two bounds, which is scale invariant by definition. This can be made clear from the l2-l1 instance optimality of Basis Pursuit (DeNoise), as described for instance in Candes' paper "The restricted isometry property and its implications for compressed sensing", or the paper from Simon Foucart and Ming-Jun Lai, "Sparsest solutions of underdetermined linear systems via ell-q minimization for 0 < q <= 1".
What is more problematic is the mutiplication of a RIP matrix by another matrix, i.e., BA seems to have a different ratio of bounds than A. This motivated research on the null space property, as in the papers of Zhang et al., e.g.
Yin Zhang, "On theory of compressive sensing via ell-1-minimization: Simple derivations and extensions"
and other related precursor studies (e.g. from J.-J. Fuchs).
Post a Comment