Sparse and Compressive Sensing Techniques

Latest papers

• What Does the Rank Buy? A Spectral and Distributional Analysis of Low-Rank Adaptation

  Babak Barazandeh · 29 September 2026

  The rank $r$ in LoRA is widely treated as a capacity control: a smaller rank is assumed to yield a simpler model that generalizes better. We show that, under hard per-factor norm budgets---the idealization of the weight decay and norm control used in practice---this intuition breaks down. The reason…

• Sample-Weighted End-to-End Trace-Norm Geometry for Multitask Learning

  Mahdi Mohammadigohari · 25 September 2026

  Multitask models combine a shared representation with task-specific outputs, but generalization bounds often control the two components separately. Such products can discard relative orientation and cancellation and can change under equivalent transformations of intermediate coordinates even when th…

• Gap-Free Streaming PCA Beyond Rank-One Updates: Near-Optimal Rates and Applications to Differential Privacy

  Anming Gu, Syamantak Kumar, Kevin Tian, Chutong Yang · 23 September 2026

  Streaming principal component analysis (PCA) seeks to recover a leading spectral subspace in a single pass over a data stream. We give a new analysis of the ubiquitous Oja's algorithm [Oja82] for the most general, gap-free variant of this problem, where no eigengap assumptions are made on the underl…

• Simpler Methods Work Better for L1 Penalized Logistic Models and Large Datasets

  Edward Raff, James Holt · 22 September 2026

  Linear models with an $L_1$-norm penalty remain state-of-the-art for high-dimensional ($d > 1,000,000$) tasks, offering a straightforward method for solving real-world industry problems. Despite their widespread use in industry and utility, many $L_1$ solvers are not effective for general use, are p…

• Iterative Atom Refinement: A Monotonicity Principle for Dictionary Learning

  Alexander Christie, Miguel Moscoso, Alexei Novikov, George Papanicolaou, Chrysoula Tsogka · 22 September 2026

  Dictionary learning seeks to recover an unknown dictionary $A$ from observations ${\bf y}_i = A{\bf x}_i$ with sparse coefficient vectors ${\bf x}_i$. We introduce the \emph{Iterative Atom Refinement} (IAR) algorithm, a simple procedure for recovering individual dictionary atoms. Starting from a ran…

• Diagonalized Attention for Individualized Regression: Latent-Row Localization and Prediction

  Borui Peng, Liwei Lin, Feifei Wang, Long Feng · 21 September 2026

  Modern text and image representations are often matrix-valued, with rows corresponding to tokens, patches, or other local feature vectors. Predictive information is often sparse but sample-specific, making classical sparse regression methods with a common support poorly suited to this heterogeneity.…

• Layerwise Decoupling for Stable Structured Sparsification of Fully Connected Layers

  Charles Kulick, Armenak Petrosyan, Sui Tang · 21 September 2026

  We propose a decoupled, layerwise method for structurally sparsifying the fully connected layers of pretrained neural networks. Rather than penalizing all layers jointly, our approach extracts shallow two-layer subnetworks, normalizes the inner weights, and applies a structured group penalty to the …

• Classification-oriented adaptive sensing via posterior sampling

  Andriy Enttsel, Maxime Rousselot, Vincent Corlay · 21 September 2026

  Recent advances in diffusion models have enabled high-performance, instance-adaptive compressed sensing through posterior sampling, without task-specific policy training. Existing methods select sensing probes by maximizing total posterior signal variance and are therefore primarily reconstruction-d…

• Out-of-Sample Embedding with Proximity Data: Projection versus Restricted Reconstruction

  Michael W. Trosset, Kaiyi Tan, Minh Tang, Carey E. Priebe · 18 September 2026

  The problem of using proximity (similarity or dissimilarity) data for the purpose of "adding a point to a vector diagram" was first studied by J.C. Gower in 1968. Since then, a number of methods -- mostly kernel methods -- have been proposed for solving what has come to be called the problem of *out…

• Near-Optimal Nonconvex Matrix Completion

  Jian-Feng Cai, Xiliang Lu, Juntao You · 16 September 2026

  We study nonconvex methods for matrix completion, the problem of recovering a low-rank matrix from a subset of its entries. Convex methods achieve sample complexity linear in the matrix dimension and the rank, up to logarithmic factors, whereas global guarantees for commonly used nonconvex methods r…

• Information-Induced Training Geometry: Exact Reduction, Canonical Completion, and Structured Expressivity

  Zavier Li · 14 September 2026

  Training data constrains optimizer geometry through the covectors visible to a declared information channel. We study how such partial information determines a full positive cometric relative to a reference and which degrees of freedom remain unidentified. Our central result resolves full-column-ran…

• A Cone-Constrained Bilinear Decomposition for Total Scaled-Gradient Variation Models

  Haibin Su, Chunlin Wu, Huibin Chang, Zhifang Liu · 2 September 2026

  The total scaled-gradient variation (TSGV) regularizer, derived from sparse modeling of piecewise-linear structures, has been shown to preserve edges and corners in image restoration. However, its highly nonconvex and nonlinear nature poses severe computational challenges, as existing methods often …

• Towards a mathematical theory of superposition

  Michael I. Ivanitskiy, John Jasper, Emily J. King, Dustin G. Mixon · 31 August 2026

  We develop a mathematical theory of superposition in neural networks using tools from frame theory and compressed sensing. In our model, a sparse binary vector \(x\) of active features is encoded through an overcomplete dictionary \(W\), and feature recovery is performed by applying \(\operatorname{…

• The Approximation Rank of Softmax Attention: Sharp Geometric Laws and Robust Interaction Dimension

  Yuhe Sui, Jianing Zhang · 31 August 2026

  Which geometry controls the rank complexity of normalized softmax attention? We study maximum-row-$\ell_1$ approximation rank, exactly the least unrestricted rank preserving every bounded vector-valued output. Two sharp worst-case laws isolate support geometry: for fixed $d$ and error $\varepsilon$,…

• Tight Majorizations and Convergence Rates of Nuclear Norm Minimization IRLS

  Christian K\"ummerle, Tomas Masak, Dominik St\"oger · 26 August 2026

  Iteratively reweighted least squares (IRLS) methods constitute a natural approach to nuclear norm minimization, but their convergence rates and the role of the weight operator have remained poorly understood. This paper establishes sharp convergence rates for IRLS methods for constrained nuclear nor…

• Physical-Support Confidence Sets for Highly Coherent Dictionaries

  Guan-Ju Peng · 21 August 2026

  Sparse pursuit after dictionary learning can yield a precise atom support even when its physical interpretation is not justified by the calibration data, especially for highly coherent dictionaries where alternative calibration-compatible dictionaries may assign different physical meanings to the sa…

• Online Generalized Sparse Regression: How Does Overparametrization Help?

  Shuoguang Yang, Qiang Sun · 19 August 2026

  Regularized sparse regression has been extensively studied in the offline setting, but online formulation remains relatively under-explored. This gap stems from four key challenges: (i) the infeasibility of dynamically updating the regularization parameter in every online round, (ii) managing storag…

• Maximum Tsallis Entropy Distributions for Robust and Efficient Sparse Learning from Correlated Data

  Kai Yang, Masoud Asgharian, Celia M. T. Greenwood · 19 August 2026

  This paper addresses the limitations of Gaussian distribution assumptions in statistical sparse learning, particularly in modeling correlated and heterogeneous data. Conventional Gaussian models often lack robustness towards outliers and underlying distribution assumptions. To overcome these limitat…

• GS$^{2}$CI: Robust Gaussian Splatting For Snapshot Compressive Imaging via Large Vision Model Priors

  Yanming Yang, Chenxi Song, Ping Wang, Xin Yuan, Chi Zhang · 14 August 2026

  Snapshot Compressive Imaging (SCI) offers an efficient solution for high-speed video acquisition and, under exposure-time camera--scene relative motion, multi-view scene capture by compressing temporal or spatial information into a single 2D measurement. While recent studies have explored SCI for 3D…

• Difference-of-Convex Regularization for Graph Learning by Differentiable Programming

  Liping Tao, Chee Wei Tan · 14 August 2026

  Laplacian-regularized minimization is fundamental in signal processing and machine learning, but is limited by the dense and ill-conditioned nature of the graph Laplacian pseudoinverse. While the Laplacian itself is sparse, its pseudoinverse is dense and often ill-conditioned, rendering direct compu…

• Fast Length-Squared Sampling for Positive-Semidefinite Matrices

  Rajarshi Bhattacharjee, Ethan N. Epperly, Cameron Musco, Aaron Tian · 14 August 2026

  We describe a simple rejection-sampling-based algorithm to perform length-squared sampling on an $n \times n$ positive-semidefinite (psd) matrix: that is, to sample a column with probability proportional to its squared $\ell_2$-norm. The algorithm runs in just $O(n)$ expected time, which is signific…

• Learning the Mathematical Property for Designing Low Mutual Coherence Binary Sensing Matrices

  Rekha, Santosh Singh, S. K. Neogy · 14 August 2026

  In this research work, we are constructing the sensing matrix, which is essential for the success of the compressive sensing technique. We have chosen a learning-based technique for the construction of the sensing matrix. The novelty and uniqueness of the proposed technique is that it does not use a…

• New Orthogonal Multiwavelet Filters Derived by Matrix Spectral Factorization

  Vasil Kolev, Todor Cooklev, Fritz Keinert · 13 August 2026

  The paper considers the construction of two new orthogonal multiwavelets with supercompact support by using the Fast Bauer's method for matrix spectral factorization on the matrix product filter of the orthogonal CL multiwavelet filter. The new multiwavelets possess orthogonality, symmetry/antisymme…

• Tight Nonasymptotic Local Convergence of Sinkhorn-Knopp

  Wenzhi Gao, Zhaonan Qu, Yinyu Ye, Madeleine Odell · 13 August 2026

  We revisit the Sinkhorn-Knopp (SK) algorithm for the matrix scaling problem. Despite extensive literature on the global convergence of SK and its variants, its local linear convergence behavior remains less understood. We address this gap by providing the first nonasymptotic local analysis of SK tha…

• PE-CSNet: An equivariant network architecture with learnable patch-based sparse representation

  Kai Li, Haitao Long, Bo Zhang, Haiwen Zhang, Zhi Zhou · 12 August 2026

  Compressive sensing (CS) enables accurate signal reconstruction from sparse measurements and is widely applied in medical imaging, remote sensing, and image compression. However, designing an effective, task-specific sparse transform and the corresponding optimization procedure for high-quality CS r…