math.OCNov 15, 2026

Relax-and-Sparsify Approximation Algorithms for Sparse Ridge Regression

Authors: Shixuan Yi, Yongchun Li

Organizations: School of Data Science, The Chinese University of Hong Kong, Shenzhen

Abstract

This paper studies sparse ridge regression in the low-rank, high-dimensional setting that often arises when data collection is expensive. By exploiting the low-rank structure, we develop approximation algorithms within a relax-and-sparsify framework: solve a convex relaxation and then sparsify its solution to satisfy the original sparsity constraint. Specifically, we establish a tight rank-dependent sparsity bound for the convex relaxation by decomposing its support into two parts. This decomposition in turn motivates two approximation strategies, parameter reduction and binary redistribution, each exploiting a different part. Experiments on synthetic and real datasets show that the binary redistribution algorithms outperform the benchmarks in most instances.

Figures & tables

Appendix figures & tables4 assets

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

CardsList
  1. Efficient Cross-Validation for Sparse Linear Regression

    Jun 26, 2023Ryan Cory-Wright, Andrés GómezModel SelectionCross-Validation

  2. D-SLR: The Disjoint Row-Sparse plus Low-Rank Decomposition

    Oct 7, 2026Vincent SzolnokyLow-Rank Matrix DecompositionLow-Rank Compression

  3. The Regularization Parameter: Sparse Precision Matrix Estimation

    Jul 7, 2026Aryan Eftekhari, Daniel Sergio Vega, Ernst-Jan Camiel Wit +1Graph Structure LearningParameter Estimation