Suppose we have a linear system $Ax=b$, where $A\in\Bbb{R}^{m\times n}$ and $b\in\Bbb R^m$. Given the possibility of multiple solutions, I want to find a least norm solution for this system by solving the problem:
$\min\{{\Vert x \Vert}_2 {}^2 $ subject to$ $ Ax=b$\}$
how can i apply coordinate descent method to this optimization problem?
You don't need numerical methods, like gradient descent, to find $x$: if $|x|^2$ is minimal subject to $Ax=b$ then the gradient of $|x|^2$ (which is $2x$) must be orthogonal to the constraint space.
But the space orthogonal to $Ax=b$ consists of rows of $A$, which means that all orthogonal vectors can be represented as $\tilde x = A^T u$ where $u\in \mathbb R^m$. Applying the constraint again we get: $$ AA^T u = b \;\;\;\; \Longrightarrow \;\;\; u =(AA^T)^{-1}b \;\;\;\; \Longrightarrow $$ $$ \tilde x = A^T(AA^T)^{-1}b $$