The pseudocode of the Subspace Pursuit method.

The goal is to represent the input with minimal reconstruction error using basis only [23]. SP differs from other iterative greedy methods in the incremental refinement of the selected basis subset. First, a representation is generated with the help of the full basis set (using pseudoinverse computations). During iteration basis are selected based on the amplitude of the corresponding coordinates of the representation. The resulting residual (difference between the original input and the approximation obtained by projecting the representation onto the input space) is then again projected back to the representation space and another set of basis are chosen. The two selected subsets are then fused (expansion) and the resulting expanded set is used again to project the original input onto the representation space. Finally a new set of basis are selected by the amplitude of the corresponding coordinates of the projection (shrinkage). Iteration stops when the norm of the residual does not decrease anymore. Notation: denotes a sub-matrix of where index set contains the indices of the selected columns. The index set of the first sorted components of a vector is denoted by .