# Why may a matrix be singular or ill-conditioned with standard learning algorithm for linear classification?

In the learning algorithm for linear classification by least square method, which find a weight vector $\hat w\in R^d$ and bias $\hat b\in R$ for a linear scoring function $f(x) = \hat w ^T x +\hat b$ for which may write the solution for $\hat w =[\sum^n_{i=1}(x_i-\bar x)(x_i -\bar x)^T]^{-1}\sum^n_{i=1}(x_i-\bar x)(x_i -\bar x)$, why may the matrix $\sum^n_{i=1}(x_i-\bar x)(x_i -\bar x)^T$ be singular or ill-conditioned ? What does that mean to be ill-conditioned ? why does it occurs when $n$ is less than the dimension of $x$ ?

• This question seems answerable directly from definitions. A matrix is singular if it is not full rank. A matrix is ill-conditioned if it has a high condition number.
– Sycorax
Jul 3, 2018 at 16:42
• @Sycorax Yes but how may $\sum^n_{i=1}(x_i-\bar x)(x_i -\bar x)$ be singular or ill-conditioned? What issues does it imply so that the standard learning algorithm may not be computable then ? Jul 3, 2018 at 16:58
• The expression you've written in your comment is not a matrix, just a sum of scalar products, so the concepts of singularity don't apply. Did you mean to include a transpose? If so, you should consult Mark L Stone's answer.
– Sycorax
Jul 3, 2018 at 17:07
• @Sycorax, there is a missing ^T typo in the last occurrence of that in the original question. I answered as though the typo hadn't occurred. Jul 3, 2018 at 17:10
• @Sycorax, I've taken the liberty of inserting the missing ^T in the OP's question. Jul 3, 2018 at 17:17

$\sum^n_{i=1}(x_i-\bar x)(x_i -\bar x)^T$ is a $d$ by $d$ matrix, where $x$ is a $d$ by $1$ vector.
For each $i$, $(x_i-\bar x)(x_i -\bar x)^T$ is a $d$ by $d$ matrix. This matrix is rank one, because it is the outer product of a vector with itself. $\sum^n_{i=1}(x_i-\bar x)(x_i -\bar x)^T$ is the sum of $n$ rank one matrices, and therefore has a rank not exceeding $n$. If $n < d$, $\sum^n_{i=1}(x_i-\bar x)(x_i -\bar x)^T$ must therefore be singular, because it can not be of full rank k.
In a sense, singular is the most ill-conditioned a matrix can be, having condition number = $\infty$. Even if $\sum^n_{i=1}(x_i-\bar x)(x_i -\bar x)^T$ is not singular, which can only be the case if $n \ge d$, it may still be ill-conditioned, thereby resulting in numerically unstable and very sensitive calculations when it is inverted or used in a linear system of equations. There are shrinkage estimators (search on this site and on the internet) to try to improve the conditioning of (sample) covariance matrices. $\sum^n_{i=1}(x_i-\bar x)(x_i -\bar x)^T$ is the sample covariance matrix, other than not dividing by $n$ or $n-1$; note that dividing by $n$ or $n-1$ does not affect the rank vs not dividing at all.