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?


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.

  • $\begingroup$ Simple question for clarification: $e$ is a $M \times 1$ vector, right? and the matrix in the saddle point system is $M+1 \times M+1$, so should there be a zero under the $e$ and to the right of the $e^T$ in that equation? $\endgroup$
    – drjrm3
    Jun 2 '15 at 13:08
  • $\begingroup$ Yup, that's correct. $\endgroup$
    – Jesse Chan
    Jun 2 '15 at 15:01
  • $\begingroup$ Finally got this implemented this evening. Works like a charm :) $\endgroup$
    – drjrm3
    Jun 7 '15 at 2:23
  • $\begingroup$ Glad to hear :) $\endgroup$
    – Jesse Chan
    Jun 7 '15 at 14:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.