Article details

Research area
Speech recognition

SIAM Journal on Matrix Analysis and it Applications, vol. 21, no. 3, pp. 797-808


Christophe Couvreur, Yoram Bresler

Optimallity of the backwards greedy algorithm for the subset selection problem


The following linear inverse problem is considered: given a full column rank m x 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 by 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.

Read/download now