Least square error problem ill conditioning

Question

I am trying to understand why I am getting an almost singular matrix in a problem I have. The problem is a simple as $$ \min_{X \in \mathbb{R}^{m,n}} \left\lVert AX - B \right\rVert_F^2 $$

Obvioulsy in constructing $A$ and $B$ there're few steps. But I can overly simplify with a toy example the step I believe is causing the issue.

Suppose you have $f(x) = e^{-\frac{x^2}{2\sigma^2}}$ and define $T_y$ as $ (T_yf)(x) = f(x - y)$. Suppose you have now $Y = \left\{ y_1, \ldots, y_n \right\}$.

Essentially I think my choice of $\sigma$ and $Y$ is such that I get something which is (numerically) linearly dependent. In theory I don't think this would happen but in practice that's my problem (numerically).

Is there maybe a theoretical/numerical method that tells me how much $ \left\{ T_y f\right\}_{y \in Y} $ are linearly indepedent? (You can imagine that you later fix $\left\{ x_1,\ldots,x_m \right\}$ and then $$ A = \begin{pmatrix} T_{y_1}(x_1) & T_{y_2}(x_1) & \ldots & T_{y_n}(x_1) \\ T_{y_1}(x_2) & T_{y_2}(x_2) & \ldots & T_{y_n}(x_2) \\ \vdots & \vdots & \ddots & \vdots \\ T_{y_1}(x_m) & T_{y_2}(x_m) & \ldots & T_{y_n}(x_m) \end{pmatrix} $$

This in my calculation (numerically) is never full rank. Note: $m >> n$.

Is there some study or measure I can use to work out better choices of $Y$ and $\sigma$?

Answer 1

At least when $c:=x_i-y_i$ does not depend on $i$, any $n\times n$ submatrix of $A$ is of the form $M=(f_c(u_i-u_j)\colon i,j=1,\dots,n\}$, where $f_c(x):=f(x+c)$. So, $\det M>0$, since the function $f_c$ (being the characteristic function of a normal distribution) is positive definite.

However, $f_c=f_{c;2}$ is only "borderline" positive definite, in the sense that for any real $p>0$, the function $f_{c;p}$ defined by the formula $f_{c;p}(x):=\exp(-|(x+c)/\sigma|^p/2)$ is positive definite if and only if $p\le2$. So then, $\det M$ may be very close to $0$ and hence $A$ may be very close to a non-full rank matrix.

The same will hold if for some permutation $\pi$ of the set $[n]:=\{1,\dots,n\}$ we have that $x_i-y_{\pi(i)}$ does not depend on $i$. A similar effect can be expected if $x_i-y_{\pi(i)}$ does not much depend on $i$ for for some permutation $\pi$ of $[n]$. Because there a great number ($n!$) of such permutations, it is likely that there is one with this "does not much depend on $i$" property.

---

There also is the general tendency for large $n\times n$ matrices to be close to singular. Indeed, the determinant is the product of the eigenvalues (repeated according to their multiplicities). So, if even one eigenvalue is very close to $0$, then the determinant may be close to $0$. This effect is exponentially strong in the number of eigenvalues close to $0$.

That is why different regularization methods, such as Tikhonov regularization and Lasso method, are used with the method of least squares.