On the Optimality of Backward Regression: Sparse Recovery and Subset Selection
| Autor: | Carla P. Gomes, Sebastian Ament |
|---|---|
| Rok vydání: | 2021 |
| Předmět: |
FOS: Computer and information sciences
Computer science Computer Science - Information Theory 02 engineering and technology 010501 environmental sciences Residual Statistics - Computation 01 natural sciences 020204 information systems 0202 electrical engineering electronic engineering information engineering FOS: Mathematics Mathematics - Numerical Analysis Pruning (decision trees) Greedy algorithm Mathematics - Optimization and Control Time complexity Selection (genetic algorithm) Computation (stat.CO) 0105 earth and related environmental sciences Sparse matrix Signal processing Information Theory (cs.IT) Numerical Analysis (math.NA) Compressed sensing Optimization and Control (math.OC) Algorithm |
| Zdroj: | ICASSP |
| DOI: | 10.48550/arxiv.2106.03235 |
| Popis: | Sparse recovery and subset selection are fundamental problems in varied communities, including signal processing, statistics and machine learning. Herein, we focus on an important greedy algorithm for these problems: Backward Stepwise Regression. We present novel guarantees for the algorithm, propose an efficient, numerically stable implementation, and put forth Stepwise Regression with Replacement (SRR), a new family of two-stage algorithms that employs both forward and backward steps for compressed sensing problems. Prior work on the backward algorithm has proven its optimality for the subset selection problem, provided the residual associated with the optimal solution is small enough. However, the existing bounds on the residual magnitude are NP-hard to compute. In contrast, our main theoretical result includes a bound that can be computed in polynomial time, depends chiefly on the smallest singular value of the matrix, and also extends to the method of magnitude pruning. In addition, we report numerical experiments highlighting crucial differences between forward and backward greedy algorithms and compare SRR against popular two-stage algorithms for compressed sensing. Remarkably, SRR algorithms generally maintain good sparse recovery performance on coherent dictionaries. Further, a particular SRR algorithm has an edge over Subspace Pursuit. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|