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:
- Condition number of a product of two matrices
- Counter example or proof that $\kappa(AB) \leq \kappa(A)\kappa(B) $
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.
