HOSVD quasioptimality for multilinear rank

Let $P_k=U_k{U}_k^{\ast }$ be the orthogonal projection used in mode $k$, and let ${\mathcal{P}}_k$ denote its action on that mode. The projections ${\mathcal{P}}_k$ commute for distinct modes, since they act on different tensor indices. By [F4], $\widehat{A}={\mathcal{P}}_1\cdots {\mathcal{P}}_{d}A$. The telescoping identity gives $A-\widehat{A}={\sum }_{k=1}^d{\mathcal{P}}_1\cdots {\mathcal{P}}_{k-1}(I-{\mathcal{P}}_k)A$. For $k<\mathrm{\ell }$, the $k$th summand lies in the kernel of ${\mathcal{P}}_k$, while the $\mathrm{\ell }$th lies in its range. These summands are orthogonal, so their squared norms add.

Each ${\mathcal{P}}_j$ is an orthogonal projection and hence a contraction: its range and kernel are orthogonal, so applying it cannot increase the squared norm. Consequently, $\mathrm{\parallel }A-\widehat{A}{\mathrm{\parallel }}_F^2={\sum }_{k=1}^d\mathrm{\parallel }{\mathcal{P}}_1\cdots {\mathcal{P}}_{k-1}(I-{\mathcal{P}}_k)A{\mathrm{\parallel }}_F^2\le {\sum }_{k=1}^d\mathrm{\parallel }(I-{\mathcal{P}}_k)A{\mathrm{\parallel }}_F^2$. By [F2], $\mathrm{\parallel }(I-{\mathcal{P}}_k)A{\mathrm{\parallel }}_F$ is the Frobenius error of truncating $A_{(k)}$ to rank $r_k$.

Fix any $B\in {\mathcal{T}}_r$. Its mode-$k$ unfolding has rank at most $r_k$ by [F1], so [F3] implies $\mathrm{\parallel }(I-{\mathcal{P}}_k)A{\mathrm{\parallel }}_F\le \mathrm{\parallel }{A}_{(k)}-B_{(k)}{\mathrm{\parallel }}_F=\mathrm{\parallel }A-B{\mathrm{\parallel }}_F$. Substitute this bound for each $k$ in step 2.1 to obtain $\mathrm{\parallel }A-\widehat{A}{\mathrm{\parallel }}_F^2\le d\mathrm{\parallel }A-B{\mathrm{\parallel }}_F^2$. Since it holds for every $B\in {\mathcal{T}}_r$, taking the infimum and square roots proves the claim.