Least squares fit for an underdetermined linear system

Question

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!

Answer 1

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