5
$\begingroup$

I would like to study the condition number of a non-square normalized matrices as function of the original non row-normalized matrix.

Let $X \in \mathbb{R}^{a \times b}$ (for $a > b$). We obtain $\hat X$ by taking all the rows of $X$ and normalizing them such that the $\ell_2$ norms of each row is $1$. We can further assume that all the rows of $X$ are $1 \leq \|x_i| \leq \alpha$

Question

I believe (and I would like to prove) that: $$\kappa(\hat X) \leq \kappa(X).$$

For me, the condition number of a matrix $X$ is defined as the ratio between the biggest and the smallest singular value of $X$, i.e.:

$$ \kappa(X) = \frac{\sigma_1}{\sigma_k} $$

where $k$ is the rank of the matrix (which can be smaller than $b$)

I think a property of matrix norm might come handy: its submultiplicativity: $$ \|AB\| \leq \|A\|\|B\|$$ from which it possible to derive the property that $$ \kappa(AB) \leq \kappa(A)\kappa(B)$$ (this is true only in some casis, see referenced questions at the bottom)

We recall that the norm of a matrix can be defined from a ($\ell_p$ which in our case is $\ell_2$)

$$ \| A \| = \max_{x \neq 0, } \frac{\|Ax\|}{\|x\|} = \max_{\|x\|=1} \|Ax\| = \sigma_1$$

My attempt:

In general, it is easy to see that $\sigma_1(\hat X) < \sigma_1(X)$, while I cannot prove that $\sigma_{min}(\hat X) > \sigma_{min}(S)$ for the smallest singular values.

This is how I approached the proof: Let me recall you that the condition number, which usually for square matrices is defined as $\kappa(X) = \|X\| \|X^{-1}\|$ for the case of non-square matrices can be better defined as the ratio between the biggest and the smallest singular value. In other words: $\kappa(X)= \|X\|\|X^+\|$ (where $X^+$ is the Moore-Penrose pseudoinverse of $X$, i.e. the matrix obtained by taking the inverse $1/\sigma_i$ of the singular values of $\sigma_i$ of $X$ ).

We can think of $X$ as the product of $\hat X$ where I left multiply by $N_X \in \mathbb{R}^{n \times n}$ , a diagonal matrix where the entry in position $ii$ is just $\|x_i\|$, i.e. the norm of row $i$. $$ X = N_X \hat X.$$

I thought that I can express the condition number as product of the norm. Unfortunately, this direction seems to lead me astray, as the inequality is in the wrong direction.

So: $\kappa(X) = \|N_X\hat X\| \|(N_X \hat X)^{+}\|=\|N_X\hat X\| \|\hat X^{+}N_X^{+} \| \leq \|N_X\| \|\hat X\| \|\hat X^{+}\|\|N_X^{+} \| $

and also $\kappa(\hat X) = \|\hat X\| \|\hat X^{-1}\|$.

Also note that $\kappa(N_X) = \kappa(N_X^{-1}) \leq \alpha$, because of our assumption on the value of the norms of the rows of $X$.

This is equivalent of asking if these two conditions are satisfied:

  • $\|\hat X\| \|\hat X^{+}\| \leq \|N_X\hat X\| \|(N_X \hat X)^{+}\| $
  • $\| \hat X^+ \| \leq \|(N\hat X)^+ \| $

It is simple to observe that: $\|\hat X\| \leq \|N\hat X\|$. This is because, by using the definition of norm of a matrix, $$\forall y \text{ s.t. } \|y\|=1 \text{ we have that } \|\hat Xy\| \leq \|N \hat Xy\|$$ because each element on the diagonal is bigger than 1. We need to see if $\|\hat X^{+}\| \leq \|(N\hat X)^+\| = \|(\hat X^{+}N^{+})\|$

I am looking here for some monotonicty properties of matrix norms, or property that can be derived from the inverse of a matrix. Am I going in the right direction? Thanks.

Reply to comment

What if we start from $N^{-1}_XX = \hat X$? Then, I would obtain $\kappa(\hat X) = \kappa(N^{-1}_X X) \leq \kappa(N^{-1}_X)\kappa(X) \leq \alpha \kappa(X) $ This does not seems helpful, because we get to the point where $$\kappa(\hat X) \leq \alpha \kappa(X)$$ and, from the previous observation, $$ \kappa(X) \leq \alpha \kappa(\hat X) $$

Experiments

I checked that this property is satisfied in two cases:

  • if we have a diagonal matrix $X$ with some random scalar in it, then the normalized version is just the identity matrix, whose condition number is 1.

  • for random matrices (random in sense of numpy.random.rand() ) it holds true that $\kappa(\hat X) \leq \kappa(X)$

Related questions

There are numerous questions around the condition number of product of matrices:

In the last question they show a counterexample for $\kappa(AB)\leq\kappa(A)\kappa(B) $ which apparently does not hold for non-square matrices.

$\endgroup$
3
  • 1
    $\begingroup$ A bit long. Please consider breaking into sections. $\endgroup$ Commented Jun 6, 2020 at 10:22
  • $\begingroup$ You start from $X = N_X \hat X$ leading to an inequality in the wrong direction. So then just start from $N_X^{-1} X = \hat X$ to get an inequality in the other direction. Does that help? $\endgroup$ Commented Jun 7, 2020 at 13:30
  • $\begingroup$ actually it does not seems helpful.. i edited the question to include the comment. probably there something i don't understand from this. $\endgroup$ Commented Jun 9, 2020 at 11:32

1 Answer 1

3
+50
$\begingroup$

Being not able to prove it I found $ \begin{pmatrix} -1 & 0\\ -1 & 1\\ 1 & 0 \end{pmatrix}$ and $ \begin{pmatrix} 4 & -2 & 3\\ -3 & -3 & -3\\ 3 & -2 & 4 \end{pmatrix} $ if you are interested in square matrices.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .