On the Optimality of the Backward Greedy Algorithm for the Subset Selection Problem

作者：Christophe Couvreur, Yoram Bresler · 发表于：SIAM Journal on Matrix Analysis and Applications · 年份：2000 · DOI：10.1137/s0895479898332928 · 被引用次数：119 · 研究领域：Sparse and Compressive Sensing Techniques、Medical Image Segmentation Techniques、Machine Learning and Algorithms

The following linear inverse problem is considered: Given a full column rank m × n data matrix A, and a length m observation vector b, find the best least-squares solution to A x = b with at most r < n nonzero components. The backward greedy algorithm computes a sparse solution to A x = b by removing greedily columns from A until r columns are left. A simple implementation based on a QR downdating scheme using Givens rotations is described. The backward greedy algorithm is shown to be optimal for the subset selection problem in the sense that it selects the "correct" subset of columns from A if the perturbation of the data vector b is small enough. The results generalize to any other norm of the residual.