acceptodds
Under review as a conference paper at ICLR 2027

Mitigating Severe Ill-Conditioning in Sparse Signal Recovery via Random Gaussian Rotation

Abstract

Recovering sparse signal from an undetermined system, known as compressing sensing (CS), has been a topic with longstanding interests in many signal processing and machine learning applications. A sensing matrix with low inter-column coherence is fundamental to the identifiability of CS. In many real-world problems (e.g., magnetic resonance imaging reconstruction and genetic disease classification) however, relative sensing matrices could be extremely `fat', and naturally contain many proportional columns. Solving the resultant CS problems is notoriously fragile. This work aims to address a family of CS problems induced by such ill-conditioned sensing matrices. We propose DogRot, a plug-and-play preconditioner constructed from a designated diagonal-dominant Gaussian random rotator. Intuitively, DogRot reshapes the sensing matrix to lower its mutual coherence while preserving the sparse solution set, thereby strengthening identifiability. We rigorously establish these properties in theory and validate them extensively in practice. As a lightweight and easily integrable preconditioner, DogRot can be seamlessly combined with existing sparse recovery algorithms. Across diverse applications, our experiments show that DogRot consistently reduces mutual coherence and effectively improves the quality of sparse signal recovery.

Primary area:
optimization
Keywords:
compressed sensing, inverse problem, sparse signal recovery

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_Ly7bOpenReview ↗
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 Q=\id+NQ=\id +N, where NN 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: A→AQA\to AQ. 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: x0→Q−1x0x_0\to Q^{-1}x_0, 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 RijR_{ij} 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 AQAQ 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 nn so that ϵ\epsilon 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

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)s \ll n/\sqrt{p\log(n)}. In a typical compressed sensing regime, we have p≥Cslog⁡(n)p\geq C s\log(n). Combining those two fact, we get to s≪(n/log⁡(n))2/3s\ll (n/\log(n))^{2/3}. Hence, the approach will only work for 'very sparse' signals -- as n→∞n\to \infty, the sparsity cannot grow faster than n2/3n^{2/3}. Looking at Theorem 3.7, assuming ϵn∼1\epsilon n\sim 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.

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 n2/3n^{2/3} 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 AAT=(n/p)IpAA^T=(n/p)I_p and log⁡n=o(p)\log n=o(p), fix c=ϵn>0c=\epsilon n>0. Theorem 3.6 gives, with probability tending to one,

μ(AQ)≤μ(A)1+c+o(1).\mu(AQ)\leq\frac{\mu(A)}{1+c}+o(1).

Theorem 3.7 also guarantees dominant-support preservation for s=o(n/log⁡n)s=o(n/\log n), for signals chosen independently of QQ with exactly ss nonzero entries and uniformly bounded active-amplitude ratios.

For an asymptotic example, concatenate 16 nearby orthogonal bases, giving AAT=16IpAA^T=16I_p and initial coherence arbitrarily close to one. Let n=16p→∞n=16p\to\infty, set s=⌊n3/4⌋s=\lfloor n^{3/4}\rfloor and ϵn=1\epsilon n=1, and choose a fixed equal-amplitude signal with exactly ss active coordinates independently of QQ. Eventually, both p≥Cslog⁡np\geq Cs\log n for any fixed CC and slog⁡n/n→0s\log n/n\to0 hold. The bound μ(AQ)≤μ(A)/2+o(1)\mu(AQ)\leq\mu(A)/2+o(1) and dominant-support preservation hold jointly for the same mixer with probability tending to one. This establishes substantial decorrelation beyond the identified n2/3n^{2/3} 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-ss-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 (2,243,0)(2,243,0) at s=10s=10, DogRot reduces MC from nearly 11 to approximately 0.900.90. With this still highly coherent operator, WNNOMP's NMSE decreases from 113.52113.52 to 1.041.04, while support precision within one grid step increases from 3.333.33\\% to 23.8823.88\\%. 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.

Reviewer_NdBdOpenReview ↗
Rating
4
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies sparse signal recovery when the sensing matrix contains highly correlated columns. Such sensing matrices can arise in applications like MRI. To handle this situation, this paper propose DogRot, a random right side preconditioner of the form Q = I+S, where S is a Gaussian skew-symmetric matrix. The main idea is to use this structured random matrix to mix the columns of the original sensing matrix so that the mixed columns have lower mutual coherence, facilitating the sparse recovery. The method first obtains an auxiliary estimate from the preconditioned system, then uses it to screen candidate supports, and finally computes the coefficients using the obtained support and original sensing matrix. The theoretical analysis establishes invertibility of the proposed structured preconditioner, a geometry-dependent coherence bound, and conditions under which the exact transformed vector Q^-1 x indicates the support of the original signal. Experiments cover MRI reconstruction, localized statistical channel modeling, and gene-based disease classification, including combinations with several recovery algorithms.

Critical strengths
  1. Exact-inverse dominant-support preservation. One natural question is that after the right side mixer, although the mutual coherence is reduced, the sparse vector x is also mixed and becomes dense, then how the original sparsity is preserved. Thm 3.7 states that rather than requiring the mixed vector to remain exactly sparse, vector z = Q^-1 x, which can be separated as the superposition of a common rescaling of the original signal and a random perturbation, is able to preserve the indices of nonzeros. This provides a foundation to demonstrate the efficacy of the system, given the difficulty to characterize Q^-1 as Q^T Q only apporaches I (upon scaling) in an entrywise manner, not spectral-norm-wise.

  2. Experiments demonstrate not only coherence reduction but also overall recovery improvements within different applications.

Critical weaknesses

None

Questions for authors
  1. Thm 3.7 establishes conditions under which the s largest-magnitude entries of the exact transformed vector Q^-1 x identify the original support. Corollary 3.8 then provides a screening guarantee for any estimate \hat z with sufficiently small error |\hat z-Q^-1 x|_\infty, without the need to specify how that estimate is obtained. Given that the exact auxiliary vector is generally dense, whereas the chosen auxiliary solvers impose sparsity constraints or sparsity-promoting regularization, could the authors clarify i) the rationale for this choice, and ii) the applicability of the conditional guarantee to the solvers used in the direct screening pipeline? I understand that the auxiliary solvers are intended as candidate generators and the reported support-overlap improvements demonstrate the usefullness. But it would be helpful to understand whether these improvements occur within the regime covered by the corollary. I am thinking a small set of experiments with known ground truth and comparison of the actual output \hat z with Q^-1 x, computed using the same Q. Besides, could existing error bounds for approximately sparse recovery, applicable to a solver used in the paper, characterize this auxiliary estimation error under assumptions relevant to the experimental settings?

  2. the coherence reduction guarantee in Thm 3.6 requires R_ii < m_n and U_\delta (A,\epsilon) < \mu (A). Could the authors comment on the conservativeness and practical scope of these sufficient conditions? In particular, do they provide nontrivial guarantees in any regimes relevant to the experimental matrices and mixing scales, or is the theorem’s main role to provide structural insight into the decorrelation mechanism?

Reviewer_NX22OpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
3
Soundness
1
Read review
Paper summary

The paper proposes a technique for handling ill-conditioned sensing matrices in compressed sensing. Instead of solving the original problem y=Ax+n\mathbf{y}=\mathbf{A} \mathbf{x} + \mathbf{n}, where A\mathbf{A} is a fat sensing matrix that has a high mutual coherence, they instead propose to solve the compressed sensing problem y=AQz+n\mathbf{y}= \mathbf{A}\mathbf{Q}\mathbf{z} + \mathbf{n} with z=Q−1x\mathbf{z}=\mathbf{Q}^{-1}\mathbf{x}

The paper attempts to establish theoretical guarantees, such as probabilistic guarantees on the reduction of mutual coherence in AQ\mathbf{AQ} (Theorem 3.6), the preservation of support sparsity in x\mathbf{x} vs. $\mathbf{Q^{-1}x} $ (Theorem 3.7), and the recovery of the original signal ∥z^−Q−1x∥\lVert\mathbf{\hat z - Q^{-1}x}\rVert (Corollary 3.8).

The paper presents experimental evidence in favor of the method.

Critical strengths

The paper presents the problem and the technical solution in a mathematically well-formulated manner. However, the reviewer presently has some concerns about the effectiveness of the theoretical results presented. Resolving these doubts will be helpful in revising the assessment of the paper.

Critical weaknesses
  1. For Theorem 3.6, please argue why Rii<mnR_{ii} < m_n. Further, it is not clear where Uδ(A,ϵ)<μ(A)U_{\delta}(\mathbf{A}, \epsilon) < \mu(\mathbf{A}) is established, so that we have, μ(B)<μ(A)\mu(\mathbf{B})< \mu(\mathbf{A})

  2. For Theorem 3.7 to hold, one needs x_\min > 2 \lVert \mathbf x \rVert_2 \sqrt{\Gamma_\delta} r_{\delta}. Justifications are needed for why this should hold theoretically and, if possible, to show the same experimentally. Aparently, this requires ϵ\epsilon to balance the factor ∥x∥2log⁡4nδ\lVert \mathbf x \rVert_2 \sqrt{\log \frac{4n}{\delta}} so that R.H.S. is small enough. Making ϵ\epsilon very small in turn should hurt the effectiveness of Equation (10).

  3. And consequently, in Corollary 3.8, it is not clear why Equation (13) should hold. Can η\eta be made arbitrarily small?

  4. It is not clear what the MC of the problems in Tables 2, 3, 4, and 5 is, where DogRot is shown to outperform the baseline. Do these experimental settings actually suffer from HIM?

Questions for authors

Please see "Critical Weaknesses" section.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of Contributions and Discussion Outcomes

Dear Area Chair,

Thank you for assessing our work. We summarize our contribution, the discussion outcomes, and a key clarification of DogRot's applicability and impact.

Our Contribution

DogRot addresses sparse recovery in the highly coherent regime, where nearly indistinguishable sensing columns make support selection unreliable and coefficient estimates unstable. Our key insight is that controlled column mixing can improve the geometry presented to a recovery algorithm while retaining the dominant-coordinate information needed to locate the original support. This enables existing solvers to work with a more favorable representation of the same measurements, followed by coefficient refitting in the original system. Our geometry-dependent coherence bounds and exact-inverse support analysis explain when this mechanism works and identify the auxiliary-estimation accuracy sufficient for reliable screening.

Experiments show improved image reconstruction in magnetic resonance imaging, better support localization and coefficient-amplitude stability in localized statistical channel modeling, and higher accuracy in gene classification. These results demonstrate DogRot's practical value across distinct applications and recovery algorithms, complementing the theoretical analysis with evidence from both signal recovery and downstream tasks.

Reviewer Recognition

Reviewer NX22 explicitly recognized the work's "theoretical soundness and experimental value" after the discussion and raised the score.

Reviewer NdBd welcomed the auxiliary-estimation diagnostic and recovery-strategy explanation. They acknowledged that our high-coherence matrix construction provides a nontrivial quantitative guarantee, stated that the additions were clear, and requested their inclusion in the revised manuscript.

Reviewer Ly7b initially recognized the idea's novelty, regarded the proofs as correct, and described the validation as solid across different datasets.

Discussion Outcomes

We provided an explicit family of highly coherent, underdetermined matrices for which the coherence-reduction conditions hold at substantial mixing strength. We also demonstrated how the manuscript's support-preservation theorem applies jointly with coherence reduction in a broader sparsity regime.

The requested diagnostic compared practical auxiliary estimates with the exact transformed target and showed substantial reductions in auxiliary estimation error. The manuscript's recovery results demonstrate corresponding benefits in support localization. Across three LSCM configurations and three solvers, mean precision within one grid step (P@1) increases from 5.56% to 28.05% at sparsity 5 and from 3.31% to 26.25% at sparsity 10, approximately fivefold and eightfold improvements. Together with the reconstruction and classification results, these findings demonstrate that DogRot's geometric improvements translate into meaningful recovery and downstream benefits.

Applicability and Impact

In response to the reviewer's question, we analyzed the stronger objective of reducing coherence to the asymptotic order of Gaussian matrices. The sparsity restriction derived for that objective subsequently informed the reviewer's concern about DogRot's overall applicability and led to a lower score. However, Gaussian-order coherence is an additional theoretical benchmark, rather than a requirement for the recovery benefits demonstrated in our paper. Sufficient conditions for that stronger benchmark should therefore be distinguished from DogRot's applicability limits.

Our follow-up showed that substantial coherence reduction and exact-inverse dominant-support preservation can hold jointly over a broader sparsity range at fixed aggregate mixing strength. Reviewer Ly7b subsequently acknowledged coherence reduction in this new regime. Their latest question concerned support preservation, which we addressed by explicitly substituting the example's parameters into Theorem 3.7 of the submitted manuscript.

The experiments reinforce this distinction. The LSCM matrices remain highly coherent after mixing, yet DogRot improves support localization and coefficient estimation. Useful recovery gains therefore arise well before Gaussian-order coherence is reached. Applying the requirements of that stronger target to the method as a whole would understate its demonstrated utility and theoretical scope.

We will incorporate the additional analyses, diagnostic results, and clarifications into the revised manuscript. We respectfully ask that the final assessment consider the reviewers' recognition and the complete discussion record, including the distinction between the stronger Gaussian-order benchmark and our recovery objectives. We believe the combination of a simple practical method, theoretical analysis, and demonstrated recovery gains merits a favorable assessment.

Thank you again for your time and consideration.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.