2

If $I-X^{\top}X$ is symmetric positive definite, why is $\lVert X \rVert < 1$? It seems logically to me but why does it follow?

It's $v^{ \top} ( I - X^{ \top } X ) v = \lVert v \rVert^2 - \lVert X v \rVert^2 > 0$....

(An attempt was $- \lVert X v \rVert^2 \geq - \lVert X \rVert^2 \cdot \lVert v \rVert^2 $ but it doesn't help..)

LisaB
  • 91

3 Answers3

3

Well, $$ I - X^\top X \succ 0 \implies v^\top(I-X^\top X)v > 0 \implies \lVert v \rVert^2 > \lVert Xv\rVert^2 \implies \frac{\lVert Xv\rVert^2}{\lVert v \rVert^2} < 1, \forall v \neq 0. $$

But by the definition of the norm $$ \lVert X \rVert = \sup_{v\neq 0} \frac{\lVert X v\rVert}{\lVert v\rVert} = \max_{\lVert v\rVert=1} \{\lVert Xv\rVert\}< 1. $$

For the equivalence $$ \sup_{v\neq 0} \frac{\lVert X v\rVert}{\lVert v\rVert} = \sup_{\lVert v\rVert = 1} \{\lVert Xv\rVert\} $$ see Equivalent Definitions of the Operator Norm, The equivalence $$ \sup_{\lVert v\rVert} \{\lVert Xv\rVert\} = \max_{\lVert v\rVert} \{\lVert Xv\rVert\}, $$ follows from the fact that $X:V\to W$ is continuous, and $\{v\in V~\vert~ \lVert v \rVert = 1\}$ is a compact set (assuming that $V$ finite dimensional), as pointed out by Drew Brady.

V.S.e.H.
  • 2,724
  • This argument is not fully rigorous. $f(v) < c$ for all $v \neq 0$ does not in general imply that $\sup_{v \neq 0} f(v) < c$. – Drew Brady Feb 02 '21 at 17:38
2

Warm-up (Non-strict inequality). $\quad$ If $I-X^T X \succeq 0$, then $X^T X \preceq I$.

Therefore, we conclude that for each $\xi$ such that $\|\xi\| = 1$, $$ \|X\xi\|^2 = \xi^T X^T X \xi \leq \xi^T I \xi = \|\xi\|^2 = 1. $$ Consequently, $\|X\| = \sup_{\|\xi\| = 1} \|X \xi \| \leq 1$.

Strict inequality: $\quad$Suppose now that $I - X^T X \succ 0$. Then $X^T X \prec I$. By compactness, there exists a $\xi_\star$ of unit norm such that $$ \|X\| = \|X \xi_\star\| = \sqrt{\xi_\star^T X^T X \xi_\star} < \sqrt{\xi_\star^T I \xi_\star} = 1. $$ This gives the strict inequality as required.

Drew Brady
  • 3,399
  • The question requires $|X|<1$ – Gribouillis Feb 02 '21 at 17:33
  • @Gribouillis updated. – Drew Brady Feb 02 '21 at 17:36
  • I guess it would be nice to show the equivalence $\sup_{v\neq 0} \frac{\lVert Xv\rVert}{\lVert v\rVert}= \max_{\lVert v\rVert = 1}{ \lVert Xv \rVert}$. Otherwise your answer is just as rigorous as mine. – V.S.e.H. Feb 02 '21 at 18:16
  • There's nothing to show. They're the same set of values. I.e., Define the set $S = { |Xv|/|v| : v \neq 0}$ and $T = {|Xv| : |v| = 1}$. They're clearly the same (and therefore their suprema coincide) – Drew Brady Feb 02 '21 at 18:35
0

Suppose $X\in \mathbb{R}^{m \times n}$ and write $X^TX=Q^TDQ$ where $Q\in \mathbb{R}^{n\times n}$ is orthogonal and $D\in \mathbb{R}^{n\times n}$ is the diagonal matrix $D=\text{diag}(\lambda_1 , \ldots ,\lambda _m)$ with $\lambda _j \geq 0$ for all $1\leq j \leq n$. Since $I-X^TX=Q^T\big(I-D\big)Q$ is positive definite and $I-D=\text{diag}(1-\lambda _1 ,\ldots ,1-\lambda _n )$ we have $1-\lambda_j>0$ for all $j$. Therefore $\lambda_j \in [0,1)$ for all $j$ which means so is $M=\max_{1 \leq j \leq n}\lambda _j$.

Now choose $v\in \mathbb{R}^n, ||v||=1$ and set $w=Qv=(w, \ldots ,w_n)^T$. The orthogonality of $Q$ implies $||w||=1$ too. We get $$||Xv||^2=w^TDw=\lambda_1 w_1^2 + \dots + \lambda _n w_n^2\leq M||w||^2<1$$ Hence $||Xv||<1$ for any $v\in \mathbb{R}^n$ with $||v||=1$ and by compactness of the unit sphere in $\mathbb{R}^n$ we have the result.

Matthew H.
  • 9,191