Interpolative cur and nystrom decompositions — Examples

Any $1\times 2$ matrix satisfying $T(:,J)=1$ has the form $T=(t,1)$. The coefficient condition gives $\mathrm{\mid }t\mathrm{\mid }\le 1$, and direct multiplication gives $A-A(:,J)T=\left[\begin{array}{cc}10& 0\\ -t& 0\end{array}\right]$. Its spectral norm is the Euclidean norm of its first column, $\sqrt{100+\mathrm{\mid }t{\mathrm{\mid }}^2}\ge 10$.

The singular values of the diagonal matrix in [A1] are $10$ and $1$, so the proposed upper bound is $\sqrt{1+1\cdot (2-1)}{\sigma }_2(A)=\sqrt{2}$. Since $10>\sqrt{2}$, no such $T$ satisfies the claim.

Direct extraction gives $C=\left[\begin{array}{cc}1& 0\\ 0& 1\\ 1& 1\end{array}\right]$, $R=\left[\begin{array}{ccc}1& 0& 1\\ 0& 1& 1\end{array}\right]$, and $W=I_2$. Since $I_2$ satisfies the four Penrose equations [F3], uniqueness [F4] gives $W^{†}=I_2$; [F1] therefore gives the reconstruction $CR$.

Multiplication yields $CR=\left[\begin{array}{ccc}1& 0& 1\\ 0& 1& 1\\ 1& 1& 2\end{array}\right]=A$. The identity $I_2$ satisfies the Penrose equations [F3], hence equals $W^{†}$ by uniqueness [F4]. The third row of $A$ is the sum of the first two, and the first two are independent, so $\mathrm{rank}(A)=2=\mathrm{rank}(W)$. Hence [F2] also applies and confirms the exact skeleton CUR identity.

We have $AS=(4,0{)}^T$ and $S^{\ast }AS=[4]$. The scalar $[1\mathrm{/}4]$ satisfies all four equations [F3], so it is the Moore-Penrose inverse by uniqueness [F4]. Substitution in [F1] gives ${\widehat{A}}_{\mathrm{n}\mathrm{y}\mathrm{s}}=\mathrm{diag}(4,0)$.

Subtracting from $A$ gives $A-{\widehat{A}}_{\mathrm{n}\mathrm{y}\mathrm{s}}=\mathrm{diag}(0,1)$, which is positive semidefinite by its nonnegative diagonal entries. The general order statement [F2] also gives $0⪯{\widehat{A}}_{\mathrm{n}\mathrm{y}\mathrm{s}}⪯A$ in this instance.