# Least squares fit for an underdetermined linear system

I want fitting my data using bicubic interpolation: $$f(x,y)=\sum_{i=0}^{3}\sum_{j=0}^{3}a_{ij}x^iy^j$$ Let known $$f(0, 0)=1; f(2, 0)=1;f(1, 1)=0;f(0, 2) = 1; f(2, 2)=1$$ I used least squares method, $$min\sum_{k=1}^{5}(f(x_k, y_k)-\sum_{i=0}^{3}\sum_{j=0}^{3}a_{ij}(x_k)^i(y_k)^j)^2$$ Receiving this system: $$\forall t, s \in [0, 3]: \sum_{k=1}^{5}\sum_{i=0}^{3}\sum_{j=0}^{3}a_{ij}(x_k)^{i+t}(y_k)^{j+s} = \sum_{k=1}^{5}(x_k)^{t}(y_k)^{s}f(x_k, y_k)$$ If present as $Ax = b$: $$A = \begin{pmatrix} 1 & 1 & 1 & 1 & 1 \\ y_1 & y_2 & y_3 & y_4 & y_5 \\ . & . & . & . & .\\ (y_1)^3 & (y_2)^3 & (y_3)^3 & (y_4 )^3 & (y_5)^3 \\ x_1 & x_2 & x_3 & x_4 & x_5 \\ x_1 y_1 & x_2 y_2 & x_3 y_3 & x_4 y_4 & x_5 y_5 \\ x_1(y_1)^3 & x_2(y_2)^3 & x_3(y_3)^3 & x_4(y_4 )^3 & x_5(y_5)^3 \\ . & . & . & . & . \\ (x_1y_1)^3 & (x_2y_2)^3 & (x_3y_3)^3 & (x_4y_4 )^3 & (x_5y_5)^3 \end{pmatrix} \cdot \begin{pmatrix} 1 & y_1 & . & (y_1)^3 & x_1 & x_1y_1 & . & x_1(y_1)^3 & (x_1y_1)^3 \\ 1 & y_2 & . & (y_2)^3 & x_2 & x_2y_2 & . & x_2(y_2)^3 & (x_2y_2)^3 \\1 & y_3 & . & (y_3)^3 & x_3 & x_3y_3 & . & x_3(y_3)^3 & (x_3y_3)^3 \\ 1 & y_4 & . & (y_4)^3 & x_4 & x_4y_4 & . & x_4(y_4)^3 & (x_4y_4)^3 \\1 & y_5 & . & (y_5)^3 & x_5 & x_5y_5 & . & x_5(y_5)^3 & (x_5y_5)^3\end{pmatrix}$$ In my example, $$A = \begin{pmatrix} 1 & 1 & 1 & 1 & 1 \\ 0 & 0 & 1 & 2 & 2 \\ 0 & 0 & 1 & 4 & 4 \\ 0 & 0 & 1 & 8 & 8 \\ 0 & 2 & 1 & 0 & 2 \\ 0 & 0 & 1 & 0 & 4 \\ 0 & 0 & 1 & 0 & 8 \\ 0 & 0 & 1 & 0 & 16 \\ 0 & 4 & 1 & 0 & 4 \\ 0 & 0 & 1 & 0 & 8 \\ 0 & 0 & 1 & 0 & 16 \\ 0 & 0 & 1 & 0 & 32 \\ 0 & 8 & 1 & 0 & 8 \\ 0 & 0 & 1 & 0 & 16 \\ 0 & 0 & 1 & 0 & 32 \\ 0 & 0 & 1 & 0 & 64 \end{pmatrix} \cdot \begin{pmatrix} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 2 & 0 & 0 & 0 & 4 & 0 & 0 & 0 & 8 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 2 & 4 & 8 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 2 & 4 & 8 & 2 & 4 & 8 & 16 & 4 & 8 & 16 & 32 & 8 & 16 & 32 & 64\end{pmatrix}$$ But resulting matrix has null determinant. Please prompt me, in least squares method, coefficients matrix can be not inverted or need find mistake? Thanks!

• Do I understand that you want to fit $5$ data points using $16$ parameters (the $a_{ij}$'s) ? I suppose I am wrong somewhere or that I missed a point. – Claude Leibovici Aug 8 '15 at 13:02
• It is hard to tell if even your gradient of the error is correct. The matrices look weird (hard to see if that $A$ is fine, where is $b$?). Tracing this step by step needs more time than I have. I suggest to start with a smaller instance of the problem and fix that one first then scale up. – mvw Aug 8 '15 at 13:03
• The 16 parameters are for the bicubic. One would expect at least 16 equations to nail them down to a unique solution. I wonder too what the five unknown components of $x$ from $Ax=b$ are. – mvw Aug 8 '15 at 13:08
• @ClaudeLeibovici it is just a sample, in main task I have few hundreds of points. Number on points influenced only on coefficients in matrix A. 16 parameters for accuracy of surface. – Dmitry Aug 8 '15 at 15:24
• @mvw thanks, I try find mistake, matrix really tangled. Do not tell, least squares method always have single solution or not necessarily? – Dmitry Aug 8 '15 at 15:35

The exact solution we recover and the property of completeness suggest transcription errors in the problem statement. The following derivation is merely a guess at the original problem.

Problem Statement

We start with a set of $m=5$ measurements of the form $\left\{ x_{k}, y_{k}, f_{k} \right\}_{k=1}^{m}$ and the trial function $$f(x,y) = a_{00} + a_{10}x + a_{01}y + a_{20}x^{2} + a_{11}xy + a_{02}y^{2}.$$ (Avoid notations that produce the indeterminate form $0^{0}$.) There are $n=\frac{1}{2}(d+1)(d+2)$ terms through degree $d$. (Here $d=2$.) These basis functions are complete through order $d$.

Linear System

The linear system is \begin{align} \mathbf{A} c &= f \\ \left[ \begin{array}{cccccc} 1 & x_{1} & y_{1} & x_{1}^{2} & x_{1} y_{1} & y_{1}^{2} \\ 1 & x_{2} & y_{2} & x_{2}^{2} & x_{2} y_{2} & y_{2}^{2} \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots \\ 1 & x_{m} & y_{m} & x_{m}^{2} & x_{m} y_{m} & y_{m}^{2} \\ \end{array} \right] % \left[ \begin{array}{c} c_{00} \\ c_{10} \\ c_{01} \\ c_{20} \\ c_{11} \\ c_{02} \end{array} \right] &= % \left[ \begin{array}{c} f(x_{1},y_{1}) \\ f(x_{2},y_{2}) \\ \vdots \\ f(x_{m},y_{m}) \end{array} \right] \\ % \left[ \begin{array}{cccccc} 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 2 & 0 & 4 & 0 & 0 \\ 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 0 & 2 & 0 & 0 & 4 \\ 1 & 2 & 2 & 4 & 4 & 4 \\ \end{array} \right] \left[ \begin{array}{c} c_{00} \\ c_{10} \\ c_{01} \\ c_{20} \\ c_{11} \\ c_{02} \end{array} \right] & = \left[ \begin{array}{c} 1 \\ 1 \\ 0 \\ 1 \\ 1 \end{array} \right]. \end{align} The number of rows $m=5$, the number of columns $n=6$, and the matrix rank is $\rho=5$.

Solution

The general least squares solution for this linear system is $$c_{LS} = \mathbf{A}^{\dagger} f + \left(\mathbf{I}_{n} - \mathbf{A}^{\dagger} \mathbf{A} \right) \zeta$$ with the arbitrary vector $\zeta\in\mathbb{C}^{n}$. The pseudoinverse matrix is $$\mathbf{A}^{\dagger} = \frac{1}{40} \left[ \begin{array}{rrrrr} 40 & 0 & 0 & 0 & 0 \\ -30 & 2 & 40 & -2 & -10 \\ -30 & -2 & 40 & 2 & -10 \\ 5 & 9 & -20 & 1 & 5 \\ 10 & -10 & 0 & -10 & 10 \\ 5 & 1 & -20 & 9 & 5 \\ \end{array} \right].$$ The affine space for the solution is $$c_{LS} = \left[ \begin{array}{r} 1 \\ -1 \\ -1 \\ \frac{1}{2} \\ 0 \\ \frac{1}{2} \end{array} \right] + \alpha \left[ \begin{array}{r} 0 \\ 2 \\ -2 \\ -1 \\ 0 \\ 1 \end{array} \right]$$ where $\alpha$ is an arbitrary complex constant. This is an exact fit: $\mathbf{A}c_{LS} - f = \mathbf{0}.$ Because we are asking for 6 parameters and providing only 5 data, we will have $n - m = 1$ vectors in the null space.

The null spaces are $$\mathcal{N} \left( \mathbf{A}^{\mathrm{T}} \right) = \text{span} \left\{ \left[ \begin{array}{r} 0 \\ 2 \\ -2 \\ -1 \\ 0 \\ 1 \end{array} \right] \right\}, \qquad \mathcal{N} \left( \mathbf{A} \right) = \left\{ \mathbf{0} \right\}.$$

The title of the question which has this answer might be "Least squares fit for an underdetermined linear system".