- Rating
- 2
- Confidence
- 4
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
This article concerns the problem of compressed sensing will illconditioned matrices (that is, matrices with high mutual coherence). The article proposes to use DogRot preconditioners. The latter are matrices of the form , where is a random Gaussian skew-symmetric matrix of small norm. In contrast to many other preconditioning methods, that are applied from the left, the DogRots are applied from the right: . In this way, the columns of the matrix are mixed, and the mutual coherence can be lowered. Importantly, the DogRot does not preserve a sparse ground truth: , but as long as epsilon is small, a sparse vector will remain almost sparse (compressible).
The authors prove a number of mathematical results that verify the above intuition. The proofs are as far as am I concerned correct. They also verify their method on real-world data, where they show that as long as epsilon is correctly tuned, their method can improve recovery.
Critical strengths
The idea to precondition to the right is in my view novel. The insight that the fact that this breaks sparsity but preserves compressibility is really clever.
The validation is solid and ranges different datasets.
Critical weaknesses
The theoretical results are a bit technical (the values of the radii are not easy to decipher).
The mutual coherence is arguably not the best indicator for success of compressed sensing.
Questions for authors
The mutual coherence is known to not be the best way to measure applicability of compressed sensing (compare the square root bottleneck). Do the authors think that one can prove that a DogRot-preconditioning can improve the RIP-constants?
The method clearly has a tradeoff -- the larger the epsilon, the closer comes to a 'fully random' matrix, but the support of sparse vectors also becomes more spread out. Do the authors think there are fundamental limits here? Concretely, are there values for so that can be chosen to make it probable that the mutual coherence becomes arbitrarily close to the corresponding values for Gaussian matrices, but the compressibility still almost is preserved?
6 comments
Thank you for continuing to examine our results carefully, and we apologize for the length of our previous response. We developed the additional analysis to give a concrete mathematical answer to your question about Gaussian-level coherence and the accompanying sparsity trade-off. Your follow-up prompted us to revisit how we presented the scope of that result. The key clarification is that the scaling arises from our particular sufficient construction for reaching Gaussian-order coherence. For the same matrix family, fixed-strength mixing already guarantees substantial coherence reduction and dominant-support preservation beyond this sparsity scaling. Our experiments also demonstrate substantial recovery gains while the sensing operators remain highly coherent. We would therefore like to briefly explain these results, which directly bear on your concern about the method's applicability and impact.
For deterministic unit-column tight frames satisfying and , fix . Theorem 3.6 gives, with probability tending to one,
Theorem 3.7 also guarantees dominant-support preservation for , for signals chosen independently of with exactly nonzero entries and uniformly bounded active-amplitude ratios.
For an asymptotic example, concatenate 16 nearby orthogonal bases, giving and initial coherence arbitrarily close to one. Let , set and , and choose a fixed equal-amplitude signal with exactly active coordinates independently of . Eventually, both for any fixed and hold. The bound and dominant-support preservation hold jointly for the same mixer with probability tending to one. This establishes substantial decorrelation beyond the identified scaling under the sampling relation in your comment.
Our earlier tail-energy analysis also quantifies the cost. Under this sparsity scaling, fixed positive mixing strength leaves a nonvanishing relative best--term approximation error, even when the dominant support is preserved. This distinction motivates screening and original-domain refitting. The auxiliary representation provides candidate locations, while final amplitudes are estimated using the original matrix. Corollary 3.8 specifies the auxiliary-estimation accuracy sufficient for successful screening.
The experiments connect this distinction to recovery performance. In LSCM, configuration at , DogRot reduces MC from nearly to approximately . With this still highly coherent operator, WNNOMP's NMSE decreases from to , while support precision within one grid step increases from to . The sensitivity experiments further show that MC continues to decrease as mixing strengthens, while LSCM EMD follows a U-shaped curve and MRI PSNR deteriorates beyond the favorable intermediate range. These results demonstrate the practical value of balancing decorrelation against mixing-induced leakage.
We will make these operating regimes clearer in the revised manuscript. We also agree that higher-order RIP guarantees require further analysis of the covering argument. We hope this clarification, together with the explicit example and application results, helps you reconsider the scope and practical impact of DogRot.
Thank you again for the discussion. We would appreciate your feedback on our latest clarification of the fixed-mixing regime, including the asymptotic example and the accompanying recovery evidence. In particular, we would welcome your view on whether this addresses your concern about the method's applicability and impact. We would be glad to clarify any remaining point before the discussion closes.
I thank you for engaging so actively with my question. It was surprising to see that one can turn an almost coherent matrix into an essentially incoherent one with the help of DogRots.
As for the idea for proving a RIP-based statements, I see that it is promising, but there is a lot of work left. Passing to the partial matrices will typically involve a covering argument in the end, that might lead to an unfavorable scaling behavior.
I have to admit that it was a bit of a challenge to get through your entire answer. It is long, uses a lot of auxiliary notation, and there are some points that I do not fully understand. I remind of the request of the conference to keep rebuttals brief.
Leaving this aside, I have upon this second consideration realised a potential bigger issue that I think poses a fundamental limit to the applicability of the DogRot approach that deserves attention.
In order for the DogRot strategy to work in the setting you describe in your answers here, you need s≪n/plog(n). In a typical compressed sensing regime, we have p≥Cslog(n). Combining those two fact, we get to s≪(n/log(n))2/3. Hence, the approach will only work for 'very sparse' signals -- as n→∞, the sparsity cannot grow faster than n2/3. Looking at Theorem 3.7, assuming ϵn∼1, this seems like an issue that persists also beyond the concrete setting the authors have considered in their output.
I stand by my assessment that the idea of the paper is clear, but after this second round of considerations, I am less sure about its impact. I have therefore changed my score.