A way to solve the least squares problem with linear equality constraints at large scale, where the classical null-space, direct-elimination and augmented-system methods are ruled out because each depends on a matrix factorization costing cubic work and, in the null-space case, produces a dense basis. The constraint is first relaxed so that the feasible set is the minimizers of the constraint residual, which agrees with the equality-constrained problem when the constraints are consistent. Writing G for A-transpose-A plus C-transpose-C, the minimum-norm solution splits into two pieces: one is the weighted pseudoinverse of the constraint matrix applied to the constraint right-hand side, the other is the minimum-norm least squares solution of A restricted to the null space of the constraint matrix, and a second variant of the split replaces the first piece with the ordinary pseudoinverse. Each piece is a least squares problem for a linear operator between spaces carrying a G-weighted inner product, so each can be solved by Golub-Kahan bidiagonalization, which touches the operator only through products with it and its adjoint. Applying the operator needs a pseudoinverse of G, supplied inexactly by an inner LSQR solve, so the resulting decomposed solvers are nested inner-outer iterations that never factor A or C. The concept teaches how re-reading a constrained problem as an operator-form unconstrained one is what makes Krylov methods available, and how to state a stopping criterion for the restricted iteration.
The linear least squares problem with linear equality constraints, minimize the norm of Ax minus b subject to Cx equal to d, arises in data fitting, signal processing, control and optimization. It is…