1
$\begingroup$

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

$\endgroup$
7
  • $\begingroup$ 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. $\endgroup$
    – Sycorax
    Jul 3, 2018 at 16:42
  • $\begingroup$ @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 ? $\endgroup$ Jul 3, 2018 at 16:58
  • $\begingroup$ 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. $\endgroup$
    – Sycorax
    Jul 3, 2018 at 17:07
  • $\begingroup$ @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. $\endgroup$ Jul 3, 2018 at 17:10
  • $\begingroup$ @Sycorax, I've taken the liberty of inserting the missing ^T in the OP's question. $\endgroup$ Jul 3, 2018 at 17:17

1 Answer 1

1
$\begingroup$

$\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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.