Constrained linear least squares matrix equation

Question

It has been a while since I have done linear least squares, so forgive the simple question, but here goes:

I am attempting to find the best fit coefficients, $\{c_i\}$, of a linear combination of basis functions: $f(x) = \Sigma_j^{M} c_j g_j(x)$ for data $\{x_i,y_i\}$. Where there are $M$ basis functions and $N$ points to be fit. I know that if all I care about is the best fit, I can solve:

$(A^T \cdot A)\cdot X = (A^T \cdot B)$

where $ A_{i,j} = g_j(x_i)$ and $X = \{c_j\}$.

If, however, I want to make sure that $\Sigma c_i = 1$, where do I account for this in the matrix equation specified above?

Answer 1

This is a constrained minimization problem (with linear constraints). You can write it like

$$\min_X \frac{1}{2}\|AX-B\|^2_2 \quad \text{ s.t. } e^TX = 1$$

where $e$ is the vector of all ones. This problem is typically solved by forming the Lagrangian $L(X,\lambda)$

$$L(X,\lambda) = \frac{1}{2}\|AX-B\|^2_2 + \lambda(1-e^TX)$$

for which the constrained solution is a stationary point of the Lagrangian. Finding this involves equating the derivatives in $X$ of the first term with derivatives in $X$ of the second. In your particular problem, the derivative of the first term with respect to $X$ leads to the normal equations, and since the constraint is linear, derivatives of the second term with respect to the entries $X_i$ are just $\lambda e_i$.

Long story short, setting these derivatives equal to each other leads to solving a saddle point system

$$\left[\begin{array}{cc}A^TA & e\\e^T &\end{array}\right]\left[\begin{array}{c}X\\ \lambda\end{array}\right] = \left[\begin{array}{c}A^TB\\ 1\end{array}\right]$$

So to add a constraint, just augment your system with one extra unknown and one extra equation per constraint. The extra unknowns $\lambda$ are referred to as Lagrange multipliers - these may have some meaning, but you can usually just discard them.