3
$\begingroup$

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!

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Claude Leibovici Aug 8 '15 at 13:02
  • $\begingroup$ 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. $\endgroup$ – mvw Aug 8 '15 at 13:03
  • $\begingroup$ 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. $\endgroup$ – mvw Aug 8 '15 at 13:08
  • $\begingroup$ @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. $\endgroup$ – Dmitry Aug 8 '15 at 15:24
  • $\begingroup$ @mvw thanks, I try find mistake, matrix really tangled. Do not tell, least squares method always have single solution or not necessarily? $\endgroup$ – Dmitry Aug 8 '15 at 15:35
1
$\begingroup$

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

$\endgroup$

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.