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$?



Least square error problem ill conditioning
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](https://en.wikipedia.org/wiki/Least_squares#Tikhonov_regularization) and [Lasso method](https://en.wikipedia.org/wiki/Least_squares#Lasso_method), are used with the method of least squares.


