I'm trying to solve a rank-deficient, ill-conditioned linear system. To say, I have a linear system
$Ax = b$,
where $A$ is an extremely retangular matrix, with size of $49680\times1604$. Rank of the system matrix is $1389$, and the condition number is $3.0231\times 10^{35}$.
My current stage is using ALM dual ascent method. The system is like
$Ax = b$ $\quad$ s.t. $\quad$ $C_n = Ax$.
The augmented Lagrangian for this system is
$L_\rho(x,\mu) = ||Ax-b||^{2}_{2}+\mu^{T}(Ax-C_n)+\frac{\rho}{2}||Ax-C_n||^2_2\quad(\rho = 300)$.
I differentiated $L_\rho(x,\mu)$ with respect to $x$ to derive $x$, and put that into the $\partial L_\rho/\partial \mu$ to iterate the dual ascent. The problem here is that the result and the error is stuck in one point even from the first iteration. The result vector $x$ does not vary meaningfully during iteration. Will there be any way to improve the problem solving?
$\frac{\partial L_\rho}{\partial x} = 2A^{T}(Ax-b)+\rho A^{T}(Ax-C_n)+A^{T}\mu = 0 \quad\cdots\quad(1)$
$\frac{\partial L_\rho}{\partial \mu} = (Ax-C_n)\quad\cdots\quad(2)$
$\mu_{k+1} = \mu_k+\alpha_k\frac{\partial L_\rho}{\partial \mu}\quad\cdots\quad\textrm{Dual Ascent}$