# 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.