8 6 3 Rank Selection With Unknown Variance

1/.
Since $\widehat A_{r^*} = argmin_{rank(A)\leq r^*} ||Y-XA||^2$ and since $r^* \buildrel\triangle\over = rank(A^*)$ we get

(1)

\begin{align} ||Y-X\widehat A_{r^*}||=||Y-(PY)_{(r^*)}|| \leq ||Y-XA^*|| = ||E|| &&\square \end{align}

2/.
The $\widehat r$ estimator minimizes (6.33) hence using 1/.

(2)

\begin{align} ||Y-(PY)_{(\widehat r)}||^2 \times [\frac{1}{nT-\lambda \widehat r}] \leq ||E||^2 \times [\frac{1}{nT-\lambda r^*}] \end{align}

Rearranging the terms yields

(3)

\begin{align} ||Y-(PY)_{(\widehat r)}||^2 &\leq ||E||^2 \times [\frac{nT-\lambda \widehat r}{nT-\lambda r^*}] = ||E||^2[1-\lambda\frac{\widehat r - r^*}{nT-\lambda r^*}] &&\square \end{align}

3/.
For the first inequality, writing $||X\widehat A_\widehat r - XA^*||^2 = ||(PY)_{(\widehat r)} - Y + Y-XA^*||^2$, developping the scalar product with $Y-XA^* = E$ and using 2/. we get

(4)

\begin{align} ||X\widehat A_\widehat r - XA^*||^2 &\leq 2||E||^2+2<XA_\widehat r -(XA^*+E),E>-\frac{\lambda(\widehat r - r*)}{nT-\lambda r^*}||E||^2 \\ &\leq 2<XA_\widehat r - XA^*,E>-\frac{\lambda(\widehat r - r*)}{nT-\lambda r^*}||E||^2 &&\square \end{align}

Now since $\hat r = rank(\widehat A_\hat r)$ and $r^*=rank(A^*)$, we have $rank(\widehat A_\hat r - A^*)$ at most $\hat r + r^*$ and

(5)

\begin{align} <X\widehat A_\hat r - XA^*,E> &= <X\widehat A_\hat r - XA^*,PE> &&\text{(P projector onto span(X))} \\ &\leq ||PE||_{(2,\hat r+r^*)}||X\widehat A_\hat r - XA^*|| &&\text{(Ky-Fan inequality)} \\ &\leq 1/2( \alpha ||PE||^{2}_{(2,\hat r+r^*)}+\alpha^{-1}||X\widehat A_\hat r - XA^*||^2 ) &&\text{(square development )} \\&&\square \end{align}

4/. Since $|PE|^2_{op}$ is the greatest eigenvalue we have $||PE||^2_{(2,\hat r+r^*)} \leq (\hat r+r^*)|PE|^2_{op}$ . Pluging that into 3/. we get

(6)

\begin{align} \frac{\alpha - 1}{\alpha}||X\widehat A_\widehat r - XA^*||^2 &\leq \lambda r^* \frac {||E||^2}{nT-\lambda r^*} + \alpha r^*|PE|^2_{op}+\hat r(\alpha |PE|^2_{op}-\lambda \frac{||E||^2}{nT-\lambda r^*}) \end{align}

Which gives us the result with $-\lambda\frac{||E||^2}{nT-\lambda r^*} \leq -\lambda \frac{||E||^2}{nT} \square$

5/.
First half of the bound:
Using gaussian concentration inequality (B.2) with $|.|_{op}$ being 1-Lipschitz, with $\xi \sim Exp(1)$

(7)

\begin{align} |PE|_{op} \leq \mathbb{E}|PE|_{op}+\sigma \sqrt{2\xi} \end{align}

Since $\mathbb{E}|PE|_{op} \leq (\sqrt q+\sqrt T)\sigma$ (see Lemma 8.3),

(8)

\begin{align} E[\alpha |PE|^2_{op}-\lambda(1-\delta)^2\sigma^2]_+ & \leq E[\alpha(\sqrt T+\sqrt q+\sqrt{2\xi})^2\sigma^2-\lambda(1-\delta)^2\sigma^2]_+ \end{align}

Now using $(a+b)^2 \leq (1+\delta)a^2+(1+\delta^{-1})b^2$ we find

(9)

\begin{align} E[\alpha |PE|^2_{op}-\lambda(1-\delta)^2\sigma^2]_+ & \leq E[\alpha 2\xi \sigma^2 (1+\delta^{-1})+\alpha(\sqrt T + \sqrt q)^2\sigma^2(1+\delta)-\lambda(1-\delta)^2\sigma^2]_+ \end{align}

By definition of K and $\lambda (= K(\sqrt T + \sqrt q)^2)$ the two terms on the right make a negative therefore

(10)

\begin{align} E[\alpha |PE|^2_{op}-\lambda(1-\delta)^2\sigma^2]_+ &\leq 2\alpha \sigma^2 (1+\delta^{-1}) \end{align}

Second half of the bound:
We find

(11)

\begin{align} \mathbb{E}[(1-\delta)^2\sigma^2-\frac{||E||^2}{nT}]_+ \leq \sigma^2 \mathbb{E}[1_{(1-\delta)\sigma \geq \frac{||E||}{\sqrt{nT}}}] \end{align}

The Frobenius norm being 1-Lipschitz we use (B.2) again as a lower bound this time with $\xi' \sim Exp(1)$ that yields

(12)

\begin{align} ||E|| &\geq \mathbb{E}||E||-\sigma \sqrt{2\xi'} \\ &\geq \sigma\sqrt{nT-4}-\sigma \sqrt{2\xi'}. \text{ (see B.4)} \end{align}

Therefore we derive

(13)

\begin{align} \mathbb{E}[(1-\delta)^2\sigma^2-\frac{||E||^2}{nT}]_+ \leq \sigma^2 \mathbb{E}[1_{\sqrt{2\xi'} \geq \sqrt{nT-4} - \sqrt{nT}(1-\delta)}] \end{align}

That last sum being positive when $\delta \geq 1-\sqrt \frac{nT-4}{nT}\approx 2/(nT)$ we get equivalently

(14)

\begin{align} \mathbb{E}[(1-\delta)^2\sigma^2-\frac{||E||^2}{nT}]_+ \leq \sigma^2 \mathbb{E}[1_{2\xi' \geq \phi(\delta)}] \end{align}

where $\phi(\delta) = nT - 4 + (1-\delta)^2 nT - 2(1-\delta)\sqrt{nT}\sqrt{nT-4}$. Since $\phi(\delta) \geq \delta^2 nT -4$ we show that

(15)

\begin{align} \mathbb{E}[(1-\delta)^2\sigma^2-\frac{||E||^2}{nT}]_+ \leq \sigma^2 \mathbb{E}[1_{2\xi' \geq \delta^2 nT - 4}] = \sigma^2 e^{-\delta^2 nT/2}e^2 \end{align}

Resulting bound:
Combining the two and using $\lambda(q \wedge T) \leq 2K(T+q)(q \wedge T) \leq 4KqT \leq 4KnT$, we find under condition $\delta \geq 1-\sqrt \frac{nT-4}{nT}\approx 2/(nT)$ the following result, (Note from the author: there is two typos in this question, see the errata)

(16)

\begin{align} \mathbb{E}[\hat r(\alpha|PE|^2_{op}-\lambda\frac{||E||^2}{nT})] &\leq 2(1+\delta^{-1})\alpha(q \wedge T)\sigma^2 +4KnTe^{-\delta^2 nT/2}e^2\sigma^2 \\&\leq 2(1+\delta^{-1})\alpha(q \wedge T)\sigma^2 +8K\delta^{-2}e\sigma^2. \end{align}

The last inequation stems from the fact that $x \mapsto xe^{-x}$ is increasing till 1 then decreasing.

6/.
We derive the following bounds:
*

(17)

\begin{align} E[\lambda r^* \frac{||E||^2}{nT-\lambda r^*}] \leq K2(T+q)r^* \sigma^2 \end{align}

using $E||E||^2 = nT\sigma^2$ and $nT-\lambda r^* \geq nT$
*

(18)

\begin{align} E[\alpha r^*|PE|^2_{op}] &\leq \alpha r^* 3(\sqrt q + \sqrt T)^2\sigma^2 \\&\leq \alpha r^* 6(q + T)\sigma^2 \end{align}

using Lemma (6.3) and subsequent computations (see course notes)

Therefore

(19)

\begin{align} E[||X\widehat A_\widehat r - XA^*||^2] &\leq C_K r^*(T+q)\sigma^2 \end{align}

with $C_K = \frac{\alpha}{\alpha-1}(2K+6\alpha+2\alpha(1+\delta^{-1})+8K\delta^{-2}e^{1}) > 1$

The (6.16) error bound is by definition always inferior (rate-wise) to this one, being equal to it when the ground truth $A^*$ is plugged in. Rank selection seems to suffer from the lack of variance-related knowledge!

Remark from the author: it is actually possible to prove a bound similar to (6.16), see this paper