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

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.