Project onto overcomplete basis

Question

How can I project a vector onto an overcomplete basis? The reason for over-complete basis is to have multiple projections to choose from. I am not sure how I can calculate the projections though.

Answer 1

Introduce a matrix $W$ whose columns are the vectors in your overcomplete basis. To represent a vector $b$ as a linear combination of a small number of vectors in your overcomplete basis, you can set $x^\star = \arg \min_x \frac12 \| Wx - b \|_2^2 + \gamma \|x\|_1$. Then $Wx^\star$ is a linear combination of your basis vectors that approximates $b$. The $\ell_1$-regularization term encourages $x^\star$ to be sparse (so most components of $x^\star$ are $0$). The parameter $\gamma > 0$ controls the sparsity of $x^\star$.

The optimization problem I wrote above is called a "Lasso" problem. Many algorithms are available to solve a Lasso problem. I think the proximal gradient method is the simplest one.