Research map / Learning theory and algorithms / Matrix and tensor methods
Hardness and Algorithms for Robust and Sparse Optimization
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use approximate nearest neighbor search on two halves of candidate sparse solutions | Sparse linear regression · Noiseless exact-solution setting | runtime: O\left( nk \cdot \left( \frac{12c \cdot d \cdot \|b\|_2}{\eps} \right)^{\frac{k}{2} \cdot (1+ 1/(2c^2-1))} \right) | Helped |
| Reduce robust regression to sparse regression and apply the sparse-regression algorithm | Robust linear regression · Zero-optimum setting | runtime: O\left( nk \cdot \left( \frac{12c \cdot n \cdot \|b\|_2 }{\eps} \right)^{\frac{k}{2} \cdot (1+ 1/(2c^2-1))} \right) | Helped |
| Use random partitioning and bichromatic farthest-pair search | Sparse PCA · PSD matrix of rank r | approximation ratio: 1-\eps | Helped |
| Use diameter search for limited-alphabet sparse PCA | Sparse PCA · Limited alphabet | approximation ratio: 1-\eps | Helped |
| Use the proposed sparse PCA method instead of the cited prior algorithm | Sparse PCA · PSD matrix of rank r | runtime dependence on ε: (4/\eps)^{r} -> (1/\eps)^{r/2 + 1} | Helped |
| Allow ignoring k rows in robust regression | Robust linear regression · Worst case | randomized time lower bound: \Omega(n^{k/2+o(1)}) | Hurt |
| Use the greedy strategy of fitting all data, then removing the largest-residual point | Robust linear regression · Four-point example, k=1 | regression loss: 0 loss | Hurt |
| Use alternating minimization from a non-optimal initialization | Robust linear regression · Four-point example, k=1 | regression loss | Hurt |
Closest papers by meaning
- Robust Sparse Regression with Non-Isotropic Designs (NeurIPS 2024 · similarity 0.91)
- Structured Sparse Regression via Greedy Hard Thresholding (NeurIPS 2016 · similarity 0.90)
- Low-Rank-Sparse Subspace Representation for Robust Regression (CVPR 2017 · similarity 0.89)
- Efficient Sublinear-Regret Algorithms for Online Sparse Linear Regression with Limited Observation (NeurIPS 2017 · similarity 0.89)
- Feature Adaptation for Sparse Linear Regression (NeurIPS 2023 · similarity 0.89)
- Exact Recovery of Sparse Binary Vectors from Generalized Linear Measurements (ICML 2025 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.