The Math Behind LLS

Linearly Constrained Least Squares

LLS solves linearly constrained least squares (or LCLS) problems, which have the form:

\[\begin{split}\begin{array}{ll} \mbox{minimize} & \|Ax - b\|_2^2 \\ \mbox{subject to} & Cx = d \end{array}\end{split}\]

where the unknown variable \(x\) is a vector of size \(n\). The values for \(A\), \(b\), \(C\), and \(d\) are given and have sizes \(m\times n\), \(m\), \(p\times n\), and \(p\), respectively. LLS finds a value for \(x\) that satisfies the linear equality constraints \(Cx = d\) and minimizes the objective, the sum of the squares of the entries of \(Ax - b\).

When there are no equality constraints, LCLS reduces to the simple unconstrained least squares problem (LS):

\[\begin{array}{ll} \mbox{minimize} & \|Ax-b\|_2^2 \end{array}.\]

When the objective is absent, LCLS reduces to finding \(x\) that satisfies \(Cx=d\), i.e., solving a set of linear equations.

Solving LCLS

There is a unique solution to the LCLS problem if and only if there is a unique solution to the following system of linear equations in the variable \(x\) and a new variable \(z\):

\[\begin{split}\begin{bmatrix} 2A^TA & C^T \\ C & 0 \end{bmatrix} \begin{bmatrix} x \\ z \end{bmatrix} = \begin{bmatrix} 2A^Tb \\ d \end{bmatrix},\end{split}\]

i.e., the matrix on the left is invertible. This occurs when the matrix \(C\) has independent rows, and the matrix \(\begin{bmatrix} A\\ C\end{bmatrix}\) has indepedent columns.

When there are no equality constraints, the unconstrained least squares problem has a unique solution if and only if the system of linear equations:

\[2A^TA x = 2A^Tb\]

has a unique solution, which occurs when \(A^TA\) is invertible, i.e., the columns of \(A\) are independent.

When the objective is absent, the system of linear equations \(Cx = d\) has a unique solution if and only if \(C\) is invertible.

LLS allows you to specify an LCLS problem in a natural way. It translates your specification into the general form in this section, and then solves the appropriate set of linear equations.