I want to find the minimum-norm solution to a rank-deficient least-squares problem, subject to positivity constraints, e.g.$$\min_x\ \|x\|^2 \quad s.t.\quad Ax = b,\ x \geq 0$$where $A$ is large, sparse, rectangular, and rank deficient.What is the most efficient way of robustly solving this problem? Is there recommended code out there for doing so? If $A$ were full-rank, I could use NNLS; without the inequality constraints, I could use a sparse QR decomposition. The above optimization problem is obviously a QP, so worst-case I assume an interior point method should work well, although in the past I have had trouble getting e.g. IpOpt to work with rank-deficient equality constraint matrices.EDIT: A typical $A$ is of size 50,000 $\times$ 70,000 with 1,000,000 nonzeroes. I would prefer C code, but FORTRAN, python, etc. is fine too. For performance reasons I would like to avoid Matlab if possible.
rank-deficient NNLS
linear algebra;least squares;quadratic programming
We solve almost the same problem using the Split-Bregman algorithm (see this for implementation details). Essentially you convert the problem into $\min_x \|x\|^2+\lambda \|Ax-b^*\|+\gamma\| u -x \|$ where $u$ is $x$ with all negative values removed, and $b^*$ is $b$ with the residual added. This is then solved repeatedly, with $u$ and $b^*$ changing every iteration.I can write up the entire algorithm for you if you'd like, but it may be easier to simply look at the pseudo-code in the references.