\section{Introduction}\label{sec:intro}

Let ${\mathbf{A}}$ be an $m$-by-$n$ real-valued matrix with singular value decomposition (SVD)
\begin{equation*}
	{\mathbf{A}}=[{\mathbf{U}} \,\, {\mathbf{U}}_{\perp} ] \left[ \begin{array}{c c}
			\boldsymbol{\Sigma}_1 & 0 \\
			0 & \boldsymbol{\Sigma}_2
		\end{array} \right] \left[ \begin{array}{c}
			{\mathbf{V}}^\top \\
			{\mathbf{V}}_{\perp}^\top
		\end{array} \right],
\end{equation*}
where ${\mathbf{U}} \in \mathbb{R}^{m\times r}$, ${\mathbf{V}} \in \mathbb{R}^{n\times r}$, $[{\mathbf{U}} \,\, {\mathbf{U}}_{\perp}], [{\mathbf{V}} \,\, {\mathbf{V}}_{\perp}]$ are orthogonal and $\boldsymbol{\Sigma}_1,\boldsymbol{\Sigma}_2$ are (pseudo) diagonal matrices with decreasing singular values of ${\mathbf{A}}$. Suppose ${\mathbf{B}} = {\mathbf{A}} + {\mathbf{Z}} \in \mathbb{R}^{m \times n}$, where ${\mathbf{Z}}$ is some perturbation matrix. We similarly write down the SVD of ${\mathbf{B}}$ as
\begin{equation*}
	\begin{split}
		{\mathbf{B}} =& [\widehat{{\mathbf{U}}} \,\, \widehat{{\mathbf{U}}}_{\perp} ] \left[ \begin{array}{c c}
			\widehat{\boldsymbol{\Sigma}}_1 & 0 \\
			0 & \widehat{\boldsymbol{\Sigma}}_2
		\end{array} \right] \left[ \begin{array}{c}
			\widehat{{\mathbf{V}}}^\top \\
			\widehat{{\mathbf{V}}}_{\perp}^\top
		\end{array} \right]
	\end{split}
\end{equation*}
such that $\widehat{{\mathbf{U}}}$ and $\widehat{{\mathbf{V}}}$ share the same dimensions as ${\mathbf{U}}$ and ${\mathbf{V}}$, respectively. The relationship between the singular structures of ${\mathbf{A}}$ and ${\mathbf{B}}$ is a central topic in matrix perturbation theory. Since the seminal work by Weyl \cite{weyl1912asymptotische}, Davis-Kahan \cite{davis1970rotation}, Wedin \cite{wedin1972perturbation}, the perturbation analysis for singular values (i.e., $\boldsymbol{\Sigma}_1,\boldsymbol{\Sigma}_2$ versus $\widehat{\boldsymbol{\Sigma}}_1, \widehat{\boldsymbol{\Sigma}}_2$) and the leading singular vectors (i.e., ${\mathbf{U}},{\mathbf{V}}$ versus $\widehat{\mathbf{U}},\widehat{\mathbf{V}}$) have attracted enormous attentions. For example, \cite{vaccaro1994second,xu2002perturbation,liu2008first} studied perturbation expansion for singular value decomposition; \cite{li1998relative,li1998relative2,londre2000note,stewart2006perturbation} established the relative perturbation theory for eigenvectors of Hermitian matrices and singular vectors of general matrices;  \cite{demmel1990accurate,barlow1990computing,demmel1992jacobi,drmavc2008new} studied the numeric computation accuracy for singular values and vectors; more recently, \cite{yu2014useful,cai2018rate,cape2019two} developed several new perturbation results under specific structural assumptions motivated by emerging applications in statistics and data science. The readers are referred to \cite{stewart1990matrix,ipsen2000overview,bhatia2013matrix} for overviews of the historical development of matrix perturbation theory.

While most of the existing works focused on ${\mathbf{U}}$ and ${\mathbf{V}}$ or $\boldsymbol{\Sigma}_1$ and $\boldsymbol{\Sigma}_2$, there are fewer studies on the perturbation analysis of the true matrix ${\mathbf{A}}$ itself. In this paper, we consider the estimation of rank-$r$ matrix ${\mathbf{A}}$ (i.e., $\boldsymbol{\Sigma}_2 = 0$) via rank-$r$ truncated SVD (i.e., best rank-$r$ approximation) of ${\mathbf{B}}$: $\widehat {\mathbf{A}} := \widehat{\mathbf{U}} \widehat\boldsymbol{\Sigma}_1\widehat{\mathbf{V}}^\top$. Such a low-rank assumption and estimation method are widely used in many applications including matrix denoising \cite{gavish2014optimal,donoho2014minimax}, signal processing \cite{tufts1993estimation,jolliffe2002principal} and multivariate statistical analysis \cite{morrison1976multivariate}, etc. We focus on the estimation error in matrix Schatten-$q$ norm: $\|\widehat{{\mathbf{A}}} - {\mathbf{A}}\|_q$. A tight upper bound on $\|\widehat{{\mathbf{A}}} - {\mathbf{A}}\|_q$ can provide an important benchmark for both algorithmic and statistical analysis in the applications mentioned above; moreover, it can be used to study some other basic perturbation quantities, such as the pseudo-inverse perturbation $\|\widehat{{\mathbf{A}}}^\dagger - {\mathbf{A}}^\dagger\|_q$ \cite{wedin1973perturbation,stewart1977perturbation}.

As a starting point, it is straightforward to apply the classical perturbation bounds for singular values and vectors to obtain an upper bound on $\|\widehat{\mathbf{A}}-{\mathbf{A}}\|_q$. For example, Wedin \cite{wedin1972perturbation} proved via $\sin\Theta$ Theorem that
\begin{equation}\label{ineq: wedin matrix reconstruction}
	\| \widehat{{\mathbf{A}}} - {\mathbf{A}} \|_q \leq \|{\mathbf{Z}}\|_q \left(3 + \| {\mathbf{B}} - \widehat{\mathbf{A}}\|_q/\sigma_r({\mathbf{B}}) \right).
\end{equation}
Another way is utilizing the optimality of SVD (Eckart-Young-Mirsky Theorem) and some basic norm inequalities to obtain:
\begin{equation}\label{ineq: matrix reconstruction via q-norm}
	\| \widehat{{\mathbf{A}}} - {\mathbf{A}} \|_q \leq \| \widehat{{\mathbf{A}}} - {\mathbf{B}} \|_q + \|{\mathbf{A}} - {\mathbf{B}}\|_q \leq 2 \| {\mathbf{A}} - {\mathbf{B}}  \|_q \leq 2 \| {\mathbf{Z}}  \|_q,
\end{equation}
\begin{equation} \label{ineq: matrix reconstruction via spectral norm}
	\| \widehat{{\mathbf{A}}} - {\mathbf{A}} \|_q \leq r^{1/q} \| \widehat{{\mathbf{A}}} - {\mathbf{A}} \| \overset{\eqref{ineq: matrix reconstruction via q-norm}}\leq 2 r^{1/q} \|{\mathbf{Z}}\|.
\end{equation}

In contrast, we establish the following result in this paper:
\begin{Theorem}\label{th: low rank matrix reconstruction}
	Suppose ${\mathbf{B}} = {\mathbf{A}} + {\mathbf{Z}}$, where ${\mathbf{A}}$ is an unknown rank-$r$ matrix, ${\mathbf{B}}$ is the observation, and ${\mathbf{Z}}$ is the perturbation. Let $\widehat{{\mathbf{A}}} = \widehat{\mathbf{U}} \widehat\boldsymbol{\Sigma}_1\widehat{\mathbf{V}}^\top$ be the best rank-$r$ approximation of ${\mathbf{B}}$. Then,
	\begin{equation}\label{ineq:hat-A-A}
	\begin{split}
		\|\widehat{{\mathbf{A}}} - {\mathbf{A}}\|_q & \leq \left\{ \begin{array}{ll}
				(2^q + 1)^{1/q} \left\|{\mathbf{Z}}_{\max(r)}\right\|_q, & 1\leq q \leq 2;\\
				\sqrt{5} \left\|{\mathbf{Z}}_{\max(r)}\right\|_q, & 2\leq q < \infty;\\
				2\|{\mathbf{Z}}_{\max(r)}\|, & q=\infty.
			\end{array} \right.
	\end{split}
	\end{equation}
	Here ${\mathbf{Z}}_{\max(r)}$ is defined as the best rank-$r$ approximation of ${\mathbf{Z}}$.
\end{Theorem}
The proof of Theorem \ref{th: low rank matrix reconstruction} relies on a careful characterization of $\|P_{\widehat{\mathbf{U}}_\perp}{\mathbf{A}}\|_q$ (where $P_{\widehat {\mathbf{U}}_\perp}$ is the projection onto the subspace spanned by $\widehat{{\mathbf{U}}}_\perp$) in Theorem \ref{th:SVD-projection}, which we refer as the \emph{perturbation projection error bound}. The details will be presented in Section 2.

The established bound \eqref{ineq:hat-A-A} is sharper than the classic results \eqref{ineq: wedin matrix reconstruction}, \eqref{ineq: matrix reconstruction via q-norm} and \eqref{ineq: matrix reconstruction via spectral norm} since $\|{\mathbf{Z}}_{\max(r)}\|_q\leq \|{\mathbf{Z}}\|_q, r^{1/q}\|{\mathbf{Z}}\|$ for any ${\mathbf{Z}}$. When $m, n \gg r$ and the first $r$ singular values of ${\mathbf{Z}}$ decay fast, which commonly happens in many large-scale matrix datasets \cite{udell2019big}, $\|{\mathbf{Z}}_{\max(r)}\|_q$ can be much smaller than $\|{\mathbf{Z}}\|_q, r^{1/q}\|{\mathbf{Z}}\|$ (see an example in Section \ref{sec:main-result}) so that the upper bound of \eqref{ineq:hat-A-A} can be much smaller than \eqref{ineq: wedin matrix reconstruction}, \eqref{ineq: matrix reconstruction via q-norm} and \eqref{ineq: matrix reconstruction via spectral norm}.

Then, we further introduce two lower bounds to justify the tightness of the upper bound in Theorem \ref{th: low rank matrix reconstruction}. Specifically for any $\epsilon > 0$, $1\leq q \leq \infty$, we construct a triplet of matrices $({\mathbf{A}},{\mathbf{Z}},{\mathbf{B}})$ such that
\begin{equation}\label{ineq:general-lower-bound}
	\|\widehat{{\mathbf{A}}} - {\mathbf{A}}\|_q \geq ((2^q + 1)^{1/q} - \epsilon)\|{\mathbf{Z}}_{\max(r)}\|_q >0,
\end{equation}
which suggests that the constant in \eqref{ineq:hat-A-A} cannot be further improved for $q\in [1, 2]\cup\{\infty\}$. In addition, we introduce an estimation error lower bound to show that the rank-$r$ truncated SVD estimator (i.e., $\widehat {\mathbf{A}}$) is minimax rate-optimal over the class of all rank-$r$ matrices.

As a byproduct of the theory in this paper, we derive a subspace (singular vectors) sin$\Theta$ perturbation bound (definition of Schatten-$q$ sin$\Theta$ distance is in Section \ref{sec: notation}):
$$\max\left\{\|\sin \Theta(\widehat{{\mathbf{U}}}, {\mathbf{U}})\|_q, \|\sin \Theta(\widehat{{\mathbf{V}}}, {\mathbf{V}})\|_q\right\} \leq \frac{2\| {\mathbf{Z}}_{\max(r)} \|_q }{\sigma_r({\mathbf{A}})}.$$
This bound is ``user-friendly" as it is free of ${\mathbf{B}}$, $\widehat{\mathbf{U}}$, and $\widehat{\mathbf{V}}$, which are often perturbed and uncontrolled quantities in practice (see more discussions in Section \ref{sec:wedin}).

The rest of this paper is organized as follows. After a brief introduction on notation and preliminaries in Section \ref{sec: notation}, we present the proof of Theorem \ref{th: low rank matrix reconstruction} in Section  \ref{sec:main-result} and develop the corresponding lower bounds in Section \ref{sec:lower-bound}. The new $\sin\Theta$ perturbation analysis is done in Section \ref{sec:wedin}. We provide numerical studies to corroborate our theoretical findings in Section \ref{sec: numerical study}. Conclusion and discussions are made in Section \ref{sec: conclusion}. Additional technical results and proofs are collected in Section \ref{sec:additional-proof}.

\subsection{Notation and Preliminaries} \label{sec: notation}

The following notation will be used throughout this paper. The lowercase letters (e.g., $a, b$), lowercase boldface letters (e.g., $\u, \v$), uppercase boldface letters (e.g., ${\mathbf{U}}, {\mathbf{V}}$) are used to denote scalars, vectors, matrices, respectively. For any two numbers $a,b$, let $a \wedge b = \min\{a,b\}$, $a \vee b = \max\{a,b\}$. For any matrix ${\mathbf{A}} \in \mathbb{R}^{m\times n}$ with singular value decomposition $\sum_{i=1}^{m \land n} \sigma_i({\mathbf{A}})\u_i \v_i^\top$, let ${\mathbf{A}}_{\max(r)}= \sum_{i=1}^{r} \sigma_i({\mathbf{A}})\u_i \v_i^\top$ be the best rank-$r$ approximation of ${\mathbf{A}}$, and ${\mathbf{A}}_{\max(-r)} = \sum_{i=r+1}^{m \land n} \sigma_i({\mathbf{A}})\u_i \v_i^\top$ be the remainder. For $q \in [1, \infty]$, the Schatten-$q$ norm of matrix ${\mathbf{A}}$ is defined as $\|{\mathbf{A}}\|_q := \left( \sum_{i=1}^{m \land n} \sigma^q_i({\mathbf{A}})  \right)^{1/q}$. Especially, Frobenius norm $\|\cdot\|_F$ and spectral norm $\|\cdot\|$ are Schatten-$2$ norm and -$\infty$ norm, respectively. In addition, let ${\mathbf{I}}_r$ be the $r$-by-$r$ identity matrix. Let $\mathbb{O}_{r}$ be the set of $r$-by-$r$ orthogonal matrices, $\mathbb{O}_{p, r} = \{{\mathbf{U}} \in \mathbb R^{p\times r}: {\mathbf{U}}^\top {\mathbf{U}}={\mathbf{I}}_r\}$ be the set of all $p$-by-$r$ matrices with orthonormal columns. For any ${\mathbf{U}}\in \mathbb{O}_{p, r}$, $P_{{\mathbf{U}}} = {\mathbf{U}}\U^\top$ is the projection matrix onto the column span of ${\mathbf{U}}$. We also use ${\mathbf{U}}_\perp\in \mathbb{O}_{p, p-r}$ to represent the orthonormal complement of ${\mathbf{U}}$. We use bracket subscripts to denote sub-matrices. For example, ${\mathbf{A}}_{[i_1,i_2]}$ is the entry of ${\mathbf{A}}$ on the $i_1$-th row and $i_2$-th column; ${\mathbf{A}}_{[(r+1):m, :]}$ contains the $(r+1)$-th to the $m$-th rows of ${\mathbf{A}}$.

We use the $\sin \Theta$ norm to quantify the distance between singular subspaces. Suppose ${\mathbf{U}}_1$ and ${\mathbf{U}}_2$ are two $p$-by-$r$ matrices with orthonormal columns. Let the singular values of ${\mathbf{U}}_1^\top {\mathbf{U}}_2$ be $\sigma_1 \geq \sigma_2 \geq \ldots \geq \sigma_r \geq 0$. Then $\Theta({\mathbf{U}}_1, {\mathbf{U}}_2)$ is defined as a diagonal matrix with principal angles between ${\mathbf{U}}_1$ and ${\mathbf{U}}_2$:
$$\Theta({\mathbf{U}}_1, {\mathbf{U}}_2) = {\rm diag}\left( \cos^{-1} (\sigma_1), \ldots, \cos^{-1} (\sigma_r) \right).$$
Then the Schatten-$q$ $\sin\Theta$ distance is defined as
\begin{equation}\label{label:Schatten-q-distance}
\|\sin\Theta({\mathbf{U}}_1, {\mathbf{U}}_2)\|_q = \left\|{\rm diag}(\sin \cos^{-1}(\sigma_1), \ldots, \sin \cos^{-1}(\sigma_r) )\right\|_q = \left(\sum_{i=1}^r (1-\sigma_r^2)^{q/2}\right)^{1/q}.
\end{equation}
Importantly, $\| {\mathbf{U}}_{1 \perp}^\top {\mathbf{U}}_2\|_q = \left\| \sin \Theta({\mathbf{U}}_1, {\mathbf{U}}_2) \right\|_q$ for any $q \in [1,\infty]$ \cite[Lemma 2.1]{li1998relative2}. Several basic properties of the Schatten-$q$ sin$\Theta$ distance are established in Lemma \ref{lm: spectral of sin theta} in Section \ref{sec:additional-proof}.

\section{Proof of Theorem \ref{th: low rank matrix reconstruction}}\label{sec:main-result}

We first introduce the following Theorem \ref{th:SVD-projection}, which quantifies the projection error $\|P_{\widehat{{\mathbf{U}}}_\perp}{\mathbf{A}}\|_q$ (or $\|{\mathbf{A}} P_{\widehat{{\mathbf{V}}}_\perp}\|_q$) under the perturbation model. This result plays a crucial role in the proof of Theorem \ref{th: low rank matrix reconstruction} and may also be of independent interest.
\begin{Theorem}[A perturbation projection error bound]\label{th:SVD-projection}
	Suppose ${\mathbf{B}} = {\mathbf{A}} + {\mathbf{Z}}$ for some rank-$r$ matrix ${\mathbf{A}}$ and perturbation matrix ${\mathbf{Z}}$. Then for any $q \in [1, \infty]$,
 	\begin{equation}\label{ineq:P_U-P_V}
 	\max\left\{\|P_{\widehat{{\mathbf{U}}}_\perp}{\mathbf{A}}\|_q,\|{\mathbf{A}} P_{\widehat{{\mathbf{V}}}_\perp}\|_q \right\} \leq 2 \|{\mathbf{Z}}_{\max(r)}\|_q.
 	\end{equation}
\end{Theorem}

Next, the following Lemma \ref{lm:partition-l_q-norm} characterizes the Schatten-$q$ norm of matrix orthogonal projections.
\begin{Lemma}\label{lm:partition-l_q-norm}
Suppose ${\mathbf{A}},{\mathbf{B}}\in \mathbb{R}^{m\times n}$, ${\mathbf{U}}\in \mathbb{O}_{m, r}$, $q\geq 1$. Then,
$$\|P_{\mathbf{U}}{\mathbf{A}} + P_{{\mathbf{U}}_\perp} {\mathbf{B}}\|_q \leq \left\{
\begin{array}{ll}
\left(\|P_{\mathbf{U}}{\mathbf{A}}\|_q^2 + \|P_{{\mathbf{U}}_\perp}{\mathbf{B}}\|_q^2\right)^{1/2}, & 2\leq q\leq \infty;\\
\left(\|P_{\mathbf{U}}{\mathbf{A}}\|_q^q + \|P_{{\mathbf{U}}_\perp}{\mathbf{B}}\|_q^q\right)^{1/q}, & 1\leq q \leq 2.
\end{array}
\right.$$
\end{Lemma}
\begin{proof}[Proof of Lemma \ref{lm:partition-l_q-norm}]
Let ${\mathbf{T}} = P_{\mathbf{U}}{\mathbf{A}} + P_{{\mathbf{U}}_\perp} {\mathbf{B}}$. We construct ${\mathbf{T}}_1 = P_{{\mathbf{U}}} {\mathbf{T}} = P_{\mathbf{U}}{\mathbf{A}}$, ${\mathbf{T}}_2 = P_{{\mathbf{U}}_\perp} {\mathbf{T}} = P_{{\mathbf{U}}_\perp} {\mathbf{B}}$. First we have ${\mathbf{T}}^\top {\mathbf{T}} = {\mathbf{T}}_1^\top {\mathbf{T}}_1 + {\mathbf{T}}_2^\top {\mathbf{T}}_2$. So for $p \geq 1$
\begin{equation*}
	\|{\mathbf{T}}\|_{2p}^2 = \|{\mathbf{T}}^\top {\mathbf{T}}\|_p = \|{\mathbf{T}}_1^\top {\mathbf{T}}_1 + {\mathbf{T}}_2^\top {\mathbf{T}}_2\|_p \leq \|{\mathbf{T}}_1^\top {\mathbf{T}}_1\|_p + \|{\mathbf{T}}_2^\top {\mathbf{T}}_2\|_p = \|{\mathbf{T}}_1\|_{2p}^2 + \|{\mathbf{T}}_2\|_{2p}^2,
\end{equation*} and this proves the first part.

For the second part, note that when $q = 1$, the inequality holds by triangle inequality. Next we show the inequality holds when $1 < q \leq 2$. Let ${\mathbf{X}} = \begin{bmatrix} ({\mathbf{T}}_1^\top {\mathbf{T}}_1)^{1/2} & ({\mathbf{T}}_2^\top {\mathbf{T}}_2)^{1/2}
	\end{bmatrix}$. Note that for any $1\leq p < \infty$,
\begin{equation} \label{ineq: whole big than block}
	\|{\mathbf{T}}_1^\top {\mathbf{T}} _1 + {\mathbf{T}}_2^\top {\mathbf{T}}_2\|_p^p = \| {\mathbf{X}} {\mathbf{X}}^\top \|_p^p = \|{\mathbf{X}}^\top {\mathbf{X}}\|_p^p \overset{(a)}\geq \|{\mathbf{T}}_1^\top {\mathbf{T}}_1\|_p^p + \| {\mathbf{T}}_2^\top {\mathbf{T}}_2\|_p^p,
\end{equation} where (a) is because the norm of the diagonal part of a matrix is always smaller than the norm of the whole matrix \cite{bhatia1988clarkson}. So we have
\begin{equation} \label{ineq: contraction of A}
   \|{\mathbf{T}}\|_{2p}^{2p} = 	\|{\mathbf{T}}^\top {\mathbf{T}}\|_{p}^{p} = \|{\mathbf{T}}_1^\top {\mathbf{T}} _1 + {\mathbf{T}}_2^\top {\mathbf{T}}_2\|_{p}^{p} \overset{\eqref{ineq: whole big than block}} \geq \|{\mathbf{T}}_1^\top {\mathbf{T}}_1\|_p^p + \| {\mathbf{T}}_2^\top {\mathbf{T}}_2\|_p^p = \|{\mathbf{T}}_1\|_{2p}^{2p} + \|{\mathbf{T}}_2\|_{2p}^{2p}.
\end{equation}

 Since $2 \leq 2p < \infty$ and Schatten-$q$ norm is the dual of Schatten-$2p$ norm with $1 < q \leq 2$, the second part follows by the duality argument. Specifically, we consider the linear mapping $\mathcal{A}$ such that $\mathcal{A}({\mathbf{T}})  = \begin{bmatrix} {\mathbf{T}}_1 & {\mathbf{0}}\\
{\mathbf{0}} & {\mathbf{T}}_2
\end{bmatrix}$. It is easy to verify its adjoint $\mathcal{A}^*$ satisfies $\mathcal{A}^*\left(\begin{bmatrix} {\mathbf{T}}_1 & {\mathbf{0}}\\
{\mathbf{0}} & {\mathbf{T}}_2
\end{bmatrix}\right) = {\mathbf{T}}$. From \eqref{ineq: contraction of A} we have shown for any $2\leq p < \infty$, $\|\mathcal{A}({\mathbf{T}})\|_p \leq \|{\mathbf{T}}\|_p $, i.e., $\mathcal{A}$ is contractive with respect to $\|\cdot\|_{p}$. By duality its adjoint is also a contractive map with respect to $\|\cdot\|_q$ for $1/p + 1/q = 1$ with $1 < q \leq 2$, i.e., $\|{\mathbf{T}}\|_{q}^{q} \leq \|{\mathbf{T}}_1\|_{q}^{q} + \|{\mathbf{T}}_2\|_{q}^{q}$. This finishes the proof.
\end{proof}

Next, we prove Theorem \ref{th: low rank matrix reconstruction} based on Theorem \ref{th:SVD-projection} and Lemma \ref{th: low rank matrix reconstruction}.
\begin{proof}[Proof of Theorem \ref{th: low rank matrix reconstruction}]
For $1 \leq q < \infty$, since $\widehat{{\mathbf{A}}} = {\mathbf{B}}_{\max(r)}$ and $\widehat{\mathbf{U}}$ is composed of the first $r$ left singular vectors of ${\mathbf{B}}$, we have $\widehat{\mathbf{A}} = P_{\widehat{\mathbf{U}}}{\mathbf{B}}$ and
	\begin{equation*}
		\begin{split}
			\left\| \widehat{{\mathbf{A}}} - {\mathbf{A}} \right\|_q & = \left\|P_{\widehat{{\mathbf{U}}}}{\mathbf{B}} - P_{\widehat{{\mathbf{U}}}} {\mathbf{A}} - P_{\widehat{{\mathbf{U}}}_\perp}{\mathbf{A}} \right\|_q = \left\|P_{\widehat{{\mathbf{U}}}}{\mathbf{Z}} - P_{\widehat{{\mathbf{U}}}_\perp}{\mathbf{A}} \right\|_q\\
			& \overset{(a)} \leq \left\{ \begin{array}{ll}
				\left(\left\|P_{\widehat{{\mathbf{U}}}}{\mathbf{Z}} \right\|^q_q + \left\| P_{\widehat{{\mathbf{U}}}_\perp} {\mathbf{A}} \right\|^q_q \right)^{1/q}, & 1\leq q \leq 2;\\
				\left(\left\|P_{\widehat{{\mathbf{U}}}}{\mathbf{Z}} \right\|^2_q + \left\| P_{\widehat{{\mathbf{U}}}_\perp} {\mathbf{A}} \right\|^2_q \right)^{1/2}, & 2\leq q < \infty
			\end{array}\right. \\
			& \overset{(b)}\leq \left\{ \begin{array}{ll}
				(2^q + 1)^{1/q} \left\|{\mathbf{Z}}_{\max(r)}\right\|_q, & 1\leq q \leq 2;\\
				\sqrt{5} \left\|{\mathbf{Z}}_{\max(r)}\right\|_q, & 2\leq q < \infty
			\end{array} \right.
		\end{split}
	\end{equation*}
Here, (a) is due to Lemma \ref{lm:partition-l_q-norm} and (b) is due to Theorem \ref{th:SVD-projection}. For $q = \infty$,
\begin{equation*}
\begin{split}
	\| \widehat{{\mathbf{A}}} - {\mathbf{A}} \| \leq \| \widehat{{\mathbf{A}}} - {\mathbf{B}} \| + \|{\mathbf{A}} - {\mathbf{B}}\| \overset{(a)}\leq 2 \| {\mathbf{A}} - {\mathbf{B}}  \| \leq 2 \| {\mathbf{Z}}  \| = 2\|{\mathbf{Z}}_{\max(r)}\|.
\end{split}
\end{equation*}
Here $(a)$ comes from the fact that $\widehat{\mathbf{A}}$ is the best rank-$r$ approximation of ${\mathbf{B}}$.
\end{proof}

In the rest of this section, we focus on the proof of Theorem \ref{th:SVD-projection}. To this end, we introduce several additional lemmas on the properties of matrix singular values and norms. First, the following lemma introduces a dual characterization of the truncated matrix Schatten-$q$ norm.
\begin{Lemma}[Dual representation of Truncated Schatten-$q$ norm]\label{lm: charac of Schatten-q norm}
Let ${\mathbf{X}} \in \mathbb{R}^{m \times n} (m \leq n)$ be a matrix with full singular value decomposition ${\mathbf{W}} \boldsymbol{\Lambda} {\mathbf{M}}^\top$ with ${\mathbf{W}} \in \mathbb{R}^{m \times m}, \boldsymbol{\Lambda} \in \mathbb{R}^{m \times n}, {\mathbf{M}} \in \mathbb{R}^{n \times n}$ and singular values $\lambda_1 \geq \lambda_2 \geq \ldots \geq \lambda_m$, then for any ${\mathbf{B}} \in \mathbb{R}^{m \times n}$ such that ${\rm rank}({\mathbf{B}}) \leq r \leq m$, we have
    \begin{equation}\label{ineq: inner product upper bound via q norm}
        \left| \langle {\mathbf{B}}, {\mathbf{X}} \rangle \right| \leq \|{\mathbf{B}} \|_q \left\| {\mathbf{X}}_{\max (r)}\right\|_p
    \end{equation}
    for any $q \geq 1$ and $1/p + 1/q = 1$. The equality is achieved if ${\mathbf{B}} = {\mathbf{W}}_{[:,1:r']} \boldsymbol{\Sigma} {\mathbf{M}}_{[:,1:r']}^\top$, where $r' = r \wedge {\rm rank}({\mathbf{X}})$ and $\boldsymbol{\Sigma} \in \mathbb{R}^{r' \times r'}$ is a non-zero diagonal matrix satisfying
    \begin{equation*}
        \boldsymbol{\Sigma}^q_{[1,1]}/\lambda_1^p = \cdots = \boldsymbol{\Sigma}_{[r',r']}^q/\lambda_{r'}^{p}.
    \end{equation*}
    Alternatively,
    \begin{equation}\label{eq: truncated schatten q norm}
        \|{\mathbf{X}}_{\max(r)}\|_p = \sup_{\|{\mathbf{B}}\|_q \leq 1, {\rm rank}({\mathbf{B}}) \leq r}  \langle {\mathbf{B}}, {\mathbf{X}} \rangle.
    \end{equation}
    If ${\rm rank}({\mathbf{X}}) \leq r$, then
    \begin{equation}\label{eq: schatten q norm of rank r matrix}
         \|{\mathbf{X}}\|_p = \sup_{\|{\mathbf{B}}\|_q \leq 1, {\rm rank}({\mathbf{B}}) \leq r}  \langle {\mathbf{B}}, {\mathbf{X}} \rangle.
    \end{equation}
\end{Lemma}
\begin{proof}
First, \eqref{eq: truncated schatten q norm} and \eqref{eq: schatten q norm of rank r matrix} follow from \eqref{ineq: inner product upper bound via q norm}. So we only need to prove \eqref{ineq: inner product upper bound via q norm}. Denote ${\mathbf{U}} {\mathbf{K}} {\mathbf{V}}^\top$ as a full singular value decomposition of ${\mathbf{B}}$, where ${\mathbf{U}} \in \mathbb{R}^{m \times m},  {\mathbf{K}} \in \mathbb{R}^{m \times n}, {\mathbf{V}} \in \mathbb{R}^{n \times n}$. Then
\begin{equation} \label{ineq: diag inequality}
\begin{split}
    |\langle{\mathbf{B}}, {\mathbf{X}} \rangle| =  |{\rm tr}({\mathbf{B}}^\top {\mathbf{X}})| = |{\rm tr}({\mathbf{V}} {\mathbf{K}}^\top {\mathbf{U}}^\top {\mathbf{W}} \boldsymbol{\Lambda} {\mathbf{M}}^\top)| =&  |{\rm tr}({\mathbf{K}}^\top {\mathbf{U}}^\top {\mathbf{W}} \boldsymbol{\Lambda} {\mathbf{M}}^\top {\mathbf{V}})|\\
    \leq & {\rm diag}({\mathbf{K}})^\top  |{\rm diag}({\mathbf{U}}^\top {\mathbf{W}} \boldsymbol{\Lambda} {\mathbf{M}}^\top {\mathbf{V}})|.
\end{split}
\end{equation}
Here ${\rm diag}({\mathbf{K}})$ is a vector consisting diagonal entries of ${\mathbf{K}}$ and the $|\cdot|$ is taken entrywise for a given vector.

Since ${\rm rank}({\mathbf{B}}) \leq r$, by H\"older's inequality, we have
\begin{equation}\label{ineq: holder for inner product}
    {\rm diag}({\mathbf{K}})^\top  |{\rm diag}({\mathbf{U}}^\top {\mathbf{W}} \boldsymbol{\Lambda} {\mathbf{M}}^\top {\mathbf{V}})|\leq \left( \sum_{i=1}^r {\mathbf{K}}^q_{[i,i]} \right)^{1/q} \left( \sum_{i=1}^r \left|\left( {\mathbf{U}}^\top {\mathbf{W}} \boldsymbol{\Lambda} {\mathbf{M}}^\top {\mathbf{V}} \right)_{[i,i]}\right|^p \right)^{1/p}
\end{equation}
for any $q \geq 1$, $1/p + 1/q = 1$. To finish the proof, we only need to show
\begin{equation}\label{ineq: diag value and singular value}
    \left( \sum_{i=1}^r \left|\left( {\mathbf{U}}^\top {\mathbf{W}} \boldsymbol{\Lambda} {\mathbf{M}}^\top {\mathbf{V}} \right)_{[i,i]}\right|^p \right)^{1/p} \leq \left( \sum_{i=1}^r \lambda_i^p \right)^{1/p}.
\end{equation}
To show \eqref{ineq: diag value and singular value}, we first introduce the following property of Ky Fan norm \cite{fan1949theorem} of matrix ${\mathbf{A}} \in \mathbb{R}^{m\times n}$: for any $1 \leq s \leq n \land m$
\begin{equation}\label{eq: ky norm property}
    K_s({\mathbf{A}}) := \sum_{i=1}^s \sigma_i({\mathbf{A}}) = \sup_{{\mathbf{U}} \in \mathbb{O}_{m,s}, {\mathbf{V}} \in \mathbb{O}_{n, s}} {\rm tr}({\mathbf{U}}^\top {\mathbf{A}} {\mathbf{V}}).
\end{equation}

Denote $a_1 \geq a_2 \geq \ldots \geq a_r \geq 0$ as the values of $\left\{ \left|\left( {\mathbf{U}}^\top {\mathbf{W}} \boldsymbol{\Lambda} {\mathbf{M}}^\top {\mathbf{V}} \right)_{[i,i]}\right| \right\}_{i=1}^r$ in descending order. By \eqref{eq: ky norm property}, we have
\begin{equation*}
    \sum_{i=1}^s a_i \leq K_s( {\mathbf{U}}^\top {\mathbf{W}} \boldsymbol{\Lambda} {\mathbf{M}}^\top {\mathbf{V}} ) = \sum_{i=1}^s \sigma_i\left( {\mathbf{U}}^\top {\mathbf{W}} \boldsymbol{\Lambda} {\mathbf{M}}^\top {\mathbf{V}} \right) = \sum_{i=1}^s \lambda_i, \quad \text{for }s = 1, \ldots, r.
\end{equation*} The last equality is due to the fact that ${\mathbf{U}},{\mathbf{V}},{\mathbf{W}},{\mathbf{M}}$ are all orthogonal matrices. Then equation \eqref{ineq: diag value and singular value} follows from the following Lemma \ref{lm:sequence}.
\begin{Lemma}[Karamata's inequality]\label{lm:sequence}
Suppose $x_1\geq x_2 \geq \cdots \geq x_k \geq 0$ and $y_1\geq y_2 \geq \cdots \geq y_k \geq 0$. For any $1\leq j \leq k$, $\sum_{i=1}^j x_i \leq \sum_{i=1}^j y_i$. Then for any $p\geq 1$,
$$\sum_{i=1}^k x_i^p \leq \sum_{i=1}^k y_i^p.$$
The equality holds if and only if $(x_1,\ldots, x_k) = (y_1,\ldots, y_k)$.
\end{Lemma}
\begin{proof}
See \cite[Theorem 1]{kadelburg2005inequalities}.
\end{proof}
By Lemma \ref{lm:sequence}, the equality in \eqref{ineq: diag value and singular value} holds if ${\mathbf{U}}_{[:,1:r']} = {\mathbf{W}}_{[:,1:r']}, {\mathbf{V}}_{[:,1:r']} = {\mathbf{M}}_{[:,1:r']}$; in the meantime, the equalities in \eqref{ineq: diag inequality} and \eqref{ineq: holder for inner product} hold if we further have
\begin{equation*}
    {\mathbf{K}}_{[1,1]}^q/\lambda_1^p = \cdots = {\mathbf{K}}_{[r',r']}^q/\lambda_{r'}^p
\end{equation*}
for non-zero singular values in ${\mathbf{K}}$ and ${\mathbf{K}}_{[j,j]} = 0$ for $j > r'$. This has finished the proof.
\end{proof}

Recall that a matrix norm $\|\cdot\|$ is unitarily invariant if $\|{\mathbf{A}}\| = \|{\mathbf{U}}{\mathbf{A}} {\mathbf{V}}\|$ for any matrix ${\mathbf{A}}$ and orthogonal matrices ${\mathbf{U}}, {\mathbf{V}}$. We have the following Lemmas for $\|(\cdot)_{\max(r)}\|_q$.
\begin{Lemma}\label{lem: triangle of trun schatten q}
For any $q \geq 1$, $\|(\cdot)_{\max(r)}\|_q$ is a unitarily invariant matrix norm, i.e., for any ${\mathbf{A}},{\mathbf{B}} \in \mathbb{R}^{m\times n}$ and $\lambda \in \mathbb{R}$,
\begin{itemize}
\item $\|{\mathbf{A}}_{\max(r)}\|_q \geq 0$; $\|{\mathbf{A}}_{\max(r)}\|_q=0$ if and only if ${\mathbf{A}}=0$;
\item $\|(\lambda {\mathbf{A}})_{\max(r)}\|_q = |\lambda|\cdot \|{\mathbf{A}}_{\max(r)}\|_q$, $\forall \lambda \in \mathbb{R}$;
\item $ \|\left({\mathbf{A}} + {\mathbf{B}}\right)_{\max(r)}\|_q \leq \| {\mathbf{A}}_{\max(r)} \|_q + \|{\mathbf{B}}_{\max(r)}\|_q;$
\item $\|{\mathbf{A}}_{\max(r)}\|_q = \|{\mathbf{U}}{\mathbf{A}}_{\max(r)}{\mathbf{V}}\|_q$ for any orthogonal matrices ${\mathbf{U}}$ and ${\mathbf{V}}$.
\end{itemize}
\end{Lemma}
\begin{Lemma}\label{lm: optimality of SVD in truncated Schatten-q norm}
	Given matrix ${\mathbf{A}} \in \mathbb{R}^{m \times n}$ and any non-negative integer $k \leq m \wedge n$, for any matrix ${\mathbf{M}}$ with ${\rm rank}({\mathbf{M}}) \leq r$, we have
	\begin{equation*}
		\left\|\left({\mathbf{A}}_{-\max(r)}\right)_{\max(k)} \right\|_q \leq \| \left({\mathbf{A}} - {\mathbf{M}}\right)_{\max(k)}  \|_q.
	\end{equation*}
	The equality is achieved when ${\mathbf{M}} = {\mathbf{A}}_{\max(r)}$.
\end{Lemma}
The proofs for Lemmas \ref{lem: triangle of trun schatten q} and \ref{lm: optimality of SVD in truncated Schatten-q norm} are deferred to Section \ref{sec:additional-proof}. Now we are in position to prove Theorem \ref{th:SVD-projection}.
\begin{proof}[Proof of Theorem \ref{th:SVD-projection}]
We only study $\|P_{\widehat{{\mathbf{U}}}_\perp}{\mathbf{A}}\|_q$ since the proof of the upper bound of $\|{\mathbf{A}} P_{\widehat{{\mathbf{V}}}_\perp}\|_q$ follows by symmetry. Denote $\sum_{k=1}^r \sigma_{k}({\mathbf{A}})\u_k \v_k^\top$ as a singular value decomposition of ${\mathbf{A}}$. Since ${\rm rank}(P_{\widehat{{\mathbf{U}}}_\perp}{\mathbf{A}}) \leq {\rm rank}({\mathbf{A}})= r$, for $p \geq 1$ satisfying $1/p + 1/q = 1$, we have
\begin{align
\left\|P_{\widehat{{\mathbf{U}}}_\perp}{\mathbf{A}} \right\|_q \overset{(a)}= & \sup_{\|{\mathbf{X}}\|_p \leq 1, {\rm rank}({\mathbf{X}}) \leq r } \langle P_{\widehat{{\mathbf{U}}}_\perp} {\mathbf{A}}, {\mathbf{X}} \rangle  \nonumber\\
= &   \sup_{\|{\mathbf{X}}\|_p \leq 1, {\rm rank}({\mathbf{X}}) \leq r } \langle P_{\widehat{{\mathbf{U}}}_\perp} \left({\mathbf{A}} +{\mathbf{Z}} \right) - P_{\widehat{{\mathbf{U}}}_\perp} {\mathbf{Z}} , {\mathbf{X}} \rangle \nonumber\\
\leq & \sup_{\|{\mathbf{X}}\|_p \leq 1, {\rm rank}({\mathbf{X}}) \leq r } \langle P_{\widehat{{\mathbf{U}}}_\perp} ({\mathbf{A}} +{\mathbf{Z}}), {\mathbf{X}} \rangle + \sup_{\|{\mathbf{X}}\|_p \leq 1, {\rm rank}({\mathbf{X}}) \leq r } \langle P_{\widehat{{\mathbf{U}}}_\perp} {\mathbf{Z}}, {\mathbf{X}} \rangle \nonumber\\
\overset{(b)}\leq & \sup_{\|{\mathbf{X}}\|_p \leq 1, {\rm rank}({\mathbf{X}}) \leq r } \|{\mathbf{X}}\|_p \left\|  \left(P_{\widehat{{\mathbf{U}}}_\perp} \left({\mathbf{A}} +{\mathbf{Z}} \right)\right)_{\max (r)} \right\|_q \nonumber\\
 & + \sup_{\|{\mathbf{X}}\|_p \leq 1, {\rm rank}({\mathbf{X}}) \leq r } \|{\mathbf{X}}\|_p \left\| \left(P_{\widehat{{\mathbf{U}}}_\perp} {\mathbf{Z}} \right)_{\max (r)} \right\|_q\nonumber\\
\overset{(c)}\leq & \min_{{\rm rank}({\mathbf{M}}) \leq r} \left\|  \left({\mathbf{A}} +{\mathbf{Z}} -{\mathbf{M}} \right)_{\max (r)} \right\|_q + \left\| \left(P_{\widehat{{\mathbf{U}}}_\perp} {\mathbf{Z}} \right)_{\max (r)} \right\|_q \nonumber\\
\leq & \left\| \left({\mathbf{A}} +{\mathbf{Z}}  - P_{{\mathbf{U}}}({\mathbf{A}} + {\mathbf{Z}}) \right)_{\max (r)}  \right\|_q + \left\| \left(P_{\widehat{{\mathbf{U}}}_\perp} {\mathbf{Z}} \right)_{\max (r)} \right\|_q \nonumber\\
\leq & \left\| \left(P_{{\mathbf{U}}_\perp} {\mathbf{Z}} \right)_{\max (r)} \right\|_q + \| (P_{\widehat{{\mathbf{U}}}_\perp} {\mathbf{Z}} )_{\max (r)} \|_q \label{ineq:projection}\\
\leq &  \|{\mathbf{Z}}_{\max (r)}\|_q + \|{\mathbf{Z}}_{\max (r)}\|_q \leq 2\|{\mathbf{Z}}_{\max (r)}\|_q.\nonumber
\end{align}
Here (a) (b) are due to Lemma \ref{lm: charac of Schatten-q norm} and (c) is due to Lemma \ref{lm: optimality of SVD in truncated Schatten-q norm}.
\end{proof}

We make several remarks on Theorems \ref{th: low rank matrix reconstruction} and \ref{th:SVD-projection}.

First, as discussed in Section \ref{sec:intro}, one can derive the matrix estimation error bounds relying on $\|{\mathbf{Z}}\|_q$ or $r^{1/q}\|{\mathbf{Z}}\|$ via the existing perturbation theory in the literature. The following example illustrates that our result can be much sharper when the singular values of ${\mathbf{Z}}$ has some polynomial decay.
	\begin{Example}
	    Suppose ${\mathbf{Z}}$ satisfies that $\sigma_k({\mathbf{Z}}) = k^{-1/q}$ for $q > 1$. Then
	    \begin{equation*}
	        \|{\mathbf{Z}}_{\max(r)}\|_q = \left(\sum_{k=1}^r k^{-1}\right)^{1/q} \approx (1+\log r)^{1/q},
	    \end{equation*}
        which can be much smaller than
        \begin{equation*}
	        \begin{split}
	            \|{\mathbf{Z}}\|_q & = \left(\sum_{k=1}^{m \wedge n} k^{-1}\right)^{1/q} \approx (1+\log (m \wedge n))^{1/q},\qquad    r^{1/q}\|{\mathbf{Z}}\| = r^{1/q}.
	        \end{split}
	    \end{equation*}
	\end{Example}

Second, Theorem \ref{th:SVD-projection} may not be simply implied by the classic results. For example, the classic Wedin's $\sin\Theta$ Theorem \cite{wedin1972perturbation},
\begin{equation} \label{ineq:wedin-perturbation}
	\max\left\{\|\sin\Theta({\mathbf{U}}, \widehat{{\mathbf{U}}})\|_q, \sin \Theta({\mathbf{V}}, \widehat{{\mathbf{V}}})\|_q\right\} \leq \frac{\max \{ \|{\mathbf{Z}}\widehat{{\mathbf{V}}}\|_q, \|\widehat{{\mathbf{U}}}^\top {\mathbf{Z}}\|_q \} }{\sigma_r({\mathbf{B}})},
\end{equation}
yields
\begin{equation} \label{ineq: matrix projection bound via sin Theta}
	\begin{split}
		\|P_{\widehat{{\mathbf{U}}}_\perp} {\mathbf{A}}\|_q & = \| \widehat{{\mathbf{U}}}_\perp {\mathbf{U}} \boldsymbol{\Sigma}_1 {\mathbf{V}}^\top \|_q \overset{\text{Lemma } \ref{lm: singular value characterization}}\leq \| \widehat{{\mathbf{U}}}_\perp^\top {\mathbf{U}}  \|_q \sigma_1({\mathbf{A}}) = \|\sin\Theta({\mathbf{U}}, \widehat{{\mathbf{U}}})\|_q\sigma_1({\mathbf{A}}) \\
		& \leq \max \left\{ \| {\mathbf{Z}} \widehat{{\mathbf{V}}}  \|_q, \|\widehat{{\mathbf{U}}}^\top {\mathbf{Z}}\|_q \right\} \frac{\sigma_1({\mathbf{A}}) }{\sigma_r({\mathbf{B}})}.
	\end{split}
\end{equation}
This bound \eqref{ineq: matrix projection bound via sin Theta} can be less sharp or practical for its dependency on $\sigma_1({\mathbf{A}})/\sigma_r({\mathbf{B}})$. As pointed out by \cite{udell2019big}, the spectrum of large matrix datasets arising from applications often delay fast. If the singular values of ${\mathbf{A}},{\mathbf{B}}$ decay fast, $\sigma_1({\mathbf{A}})/\sigma_r({\mathbf{B}})\gg 1$ and \eqref{ineq: matrix projection bound via sin Theta} can be loose. In contrast, our bound \eqref{ineq:P_U-P_V} in Theorem \ref{th:SVD-projection} is free of any ratio of singular values, which can be a significant advantage in practice. We will further illustrate the difference between \eqref{ineq:P_U-P_V} and \eqref{ineq: matrix projection bound via sin Theta} by simulation in Section \ref{sec: numerical matrix perturbation projection}.

Third, it is noteworthy by \eqref{ineq:projection} in the proof of Theorem \ref{th:SVD-projection}, we have actually proved
\begin{equation}\label{ineq:projection-error}
\begin{split}
	&\|P_{\widehat{{\mathbf{U}}}_\perp}{\mathbf{A}}\|_q \leq \left\|\left(P_{\widehat{\mathbf{U}}_{\perp}}{\mathbf{Z}}\right)_{\max(r)}\right\|_q + \left\|\left(P_{{\mathbf{U}}_{\perp}}{\mathbf{Z}}\right)_{\max(r)}\right\|_q \\
	& \|{\mathbf{A}} P_{\widehat{{\mathbf{V}}}_\perp}\|_q \leq   \left\|\left({\mathbf{Z}} P_{\widehat{\mathbf{V}}_{\perp}}\right)_{\max(r)}\right\|_q + \left\|\left({\mathbf{Z}} P_{{\mathbf{V}}_{\perp}}\right)_{\max(r)}\right\|_q
\end{split}
\end{equation}
under the setting of Theorem \ref{th:SVD-projection}. The bound \eqref{ineq:projection-error} can be better than the one in Theorem \ref{th:SVD-projection} in some scenarios. For example, when ${\mathbf{Z}}$ is (or is close to) ${\mathbf{U}} \Sigma_{\mathbf{Z}} {\mathbf{V}}^\top$ for some $r$-by-$r$ matrix $\Sigma_{\mathbf{Z}}$, the bound in \eqref{ineq:projection-error} is smaller than $\|{\mathbf{Z}}_{\max(r)}\|_q$. On the other hand, the proposed bound in Theorem \ref{th:SVD-projection} is strong enough for proving Theorem \ref{th: low rank matrix reconstruction}, does not involve $P_{\widehat{\mathbf{U}}_{\perp}}$ or $P_{\widehat{\mathbf{V}}_{\perp}}$, and can be more convenient to use.

\section{Lower bounds}\label{sec:lower-bound}
The following Theorem \ref{th:lower bound} shows that the error upper bound for the rank-$r$ truncated SVD estimator $\widehat {\mathbf{A}}$ in Theorem \ref{th: low rank matrix reconstruction} is sharp.
\begin{Theorem}\label{th:lower bound}
For any $\varepsilon>0$ and $q \geq 1$, there exist ${\mathbf{A}}$, ${\mathbf{B}}$, and ${\mathbf{Z}}\neq 0$ such that ${\rm rank}({\mathbf{A}}) = r$, ${\mathbf{B}}={\mathbf{A}}+{\mathbf{Z}}$, and
$$\|\widehat{{\mathbf{A}}} - {\mathbf{A}}\|_q > ((2^q+1)^{1/q}-\varepsilon)\|{\mathbf{Z}}_{\max(r)}\|_q.$$
\end{Theorem}
\begin{proof}
Without loss of generality we assume $0<\varepsilon<1$. We choose a value $\eta \in (0,  \frac{(2^q+1)^{1/q}}{(2^q+1)^{1/q} - \varepsilon} - 1)$. Define
\begin{equation*}
    {\mathbf{A}} =
    \begin{bmatrix}
        2{\mathbf{I}}_r & \mathbf{0}_{r\times r} & \mathbf{0}\\
        \mathbf{0}_{r\times r} & \mathbf{0}_{r\times r} & \mathbf{0}\\
        \mathbf{0} & \mathbf{0} & \mathbf{0}
    \end{bmatrix}, \quad {\mathbf{Z}} = \begin{bmatrix}
        -(1+\eta){\mathbf{I}}_r & \mathbf{0}_{r\times r} & \mathbf{0}\\
        \mathbf{0}_{r\times r} & {\mathbf{I}}_r & \mathbf{0}\\
        \mathbf{0} & \mathbf{0} & \mathbf{0}
    \end{bmatrix},
\end{equation*} and
\begin{equation*}
    {\mathbf{B}} = \begin{bmatrix}
    (1-\eta){\mathbf{I}}_r & \mathbf{0}_{r\times r} & \mathbf{0}\\
    \mathbf{0}_{r\times r} & {\mathbf{I}}_r & \mathbf{0}\\
    \mathbf{0} & \mathbf{0} & \mathbf{0}
    \end{bmatrix}.
\end{equation*}
Then,
\begin{equation*}
    \|\widehat{{\mathbf{A}}} - {\mathbf{A}}\|_q = \left\|\begin{bmatrix}
    -2{\mathbf{I}}_r & \mathbf{0}_{r\times r}\\
    \mathbf{0}_{r\times r} & {\mathbf{I}}_r
    \end{bmatrix}\right\|_q = (2^q r + r)^{1/q},\quad \|{\mathbf{Z}}_{\max(r)}\|_q = (1+\eta) r^{1/q}.
\end{equation*}
We thus have
\begin{equation*}
    \|\widehat{{\mathbf{A}}} - {\mathbf{A}}\|_q > ((2^q + 1)^{1/q} - \varepsilon)\|{\mathbf{Z}}_{\max(r)}\|_q.
\end{equation*}
\end{proof}
Theorem \ref{th: low rank matrix reconstruction} and Theorem \ref{th:lower bound} together imply that the constants in \eqref{ineq:hat-A-A} are not improvable when $1\leq q\leq 2$ and $q = \infty$. For $2 < p < \infty$, it would be an interesting future work to close the gap between the upper bound ($\sqrt{5}\|{\mathbf{Z}}_{\max(r)}\|_q$) and the lower bound ($(2^q+1)^{1/q}\|{\mathbf{Z}}_{\max(r)}\|_q$).

Apart from checking the sharpness of the upper bound \eqref{ineq:hat-A-A}, another nature question is, whether the rank-$r$ truncated SVD estimator is an optimal estimator in estimating ${\mathbf{A}}$. To answer this question, we consider the minimax estimation error lower bound among all possible data-dependent procedures $\widecheck{{\mathbf{A}}} = \widecheck{{\mathbf{A}}}({\mathbf{B}})$ (i.e., $\widecheck{{\mathbf{A}}}$ is a deterministic or random function of matrix ${\mathbf{B}}$). We specifically focus on the following class of $(\widetilde{{\mathbf{A}}}, \widetilde{{\mathbf{Z}}}, \widetilde{{\mathbf{B}}})$ triplets:
\begin{equation*}
	\mathcal{F}_r(\xi) = \left\{ (\widetilde{{\mathbf{A}}}, \widetilde{{\mathbf{Z}}},\widetilde{{\mathbf{B}}}): \widetilde{\mathbf{B}} = \widetilde{\mathbf{A}} + \widetilde{\mathbf{Z}},{\rm rank}(\widetilde{{\mathbf{A}}}) = r, \left\| \widetilde{{\mathbf{Z}}}_{\max(r)} \right\|_q \leq \xi \right\}.
\end{equation*}
Here, $\xi$ corresponds to $\left\|{\mathbf{Z}}_{\max(r)}\right\|_q$ in the context of Theorem \ref{th: low rank matrix reconstruction}.
\begin{Theorem}[Schatten-$q$ minimax lower bound] \label{th: matrix reconstruction lower bound}
For the low-rank perturbation model, if $m \wedge n \geq 2r$, then, for any $q \geq 1$, we have
	\begin{equation*}
		\inf_{\widecheck{{\mathbf{A}}}} \sup_{(\widetilde{{\mathbf{A}}}, \widetilde{{\mathbf{Z}}},\widetilde{{\mathbf{B}}}) \in \mathcal{F}_r(\xi)} \left\| \widecheck{{\mathbf{A}}} - \widetilde{{\mathbf{A}}}  \right\|_q \geq 2^{1/q-1} \xi.
	\end{equation*}
Here the infimum is taken over all the estimation procedures.
\end{Theorem}
\begin{proof}
The proof is done by construction. We construct
\begin{equation*}
	{\mathbf{Z}}_1 = \left(\begin{array}{ccc}
		  {\mathbf{0}}_{r \times r} & {\mathbf{0}} & {\mathbf{0}}\\
		{\mathbf{0}} & \frac{\xi}{r^{1/q}} {\mathbf{I}}_r & {\mathbf{0}}\\
		{\mathbf{0}} & {\mathbf{0}} & {\mathbf{0}}
	\end{array} \right),\quad \widebar{{\mathbf{A}}}_1 =  \left( \begin{array}{c c c}
		  \frac{\xi }{r^{1/q}} {\mathbf{I}}_r & {\mathbf{0}} & {\mathbf{0}}\\
		{\mathbf{0}} & {\mathbf{0}}_{r \times r} & {\mathbf{0}}\\
		{\mathbf{0}} & {\mathbf{0}} & {\mathbf{0}}
	\end{array} \right),
\end{equation*} and
\begin{equation*}
	{\mathbf{Z}}_2 =  \left( \begin{array}{c c c}
		  \frac{\xi}{ r^{1/q}}{\mathbf{I}}_r & {\mathbf{0}} & {\mathbf{0}}\\
		{\mathbf{0}} & {\mathbf{0}}_{r \times r} & {\mathbf{0}}\\
		{\mathbf{0}} & {\mathbf{0}} & {\mathbf{0}}
	\end{array} \right),\quad \widebar{{\mathbf{A}}}_2 =  \left( \begin{array}{c c c}
		  {\mathbf{0}}_{r \times r} & {\mathbf{0}} & {\mathbf{0}}\\
		{\mathbf{0}} & \frac{\xi }{r^{1/q}} {\mathbf{I}}_r & {\mathbf{0}}\\
		{\mathbf{0}} & {\mathbf{0}} & {\mathbf{0}}
	\end{array} \right).
\end{equation*}

By the construction above, we have $\| ({\mathbf{Z}}_1)_{\max(r)} \|_q = \xi$, $\|({\mathbf{Z}}_2)_{\max(r)} \|_q = \xi$, and $\widebar{{\mathbf{A}}}_1 +  {\mathbf{Z}}_1 = \widebar{{\mathbf{A}}}_2 + {\mathbf{Z}}_2$. So
\begin{equation*}
	\begin{split}
		& \inf_{\widecheck{{\mathbf{A}}}} \sup_{(\widetilde{{\mathbf{A}}}, \widetilde{{\mathbf{Z}}}, \widetilde{{\mathbf{B}}}) \in \mathcal{F}_r(\xi)} \left\| \widecheck{{\mathbf{A}}} - \widetilde{{\mathbf{A}}}  \right\|_q \geq \inf_{\widecheck{{\mathbf{A}}}} \left(\max \left\{ \| \widecheck{{\mathbf{A}}} - \widebar{{\mathbf{A}}}_1 \|_q,  \| \widecheck{{\mathbf{A}}} - \widebar{{\mathbf{A}}}_2 \|_q  \right\} \right)\\
		\geq & \frac{1}{2} \inf_{\widecheck{{\mathbf{A}}}} \left( \| \widecheck{{\mathbf{A}}} - \widebar{{\mathbf{A}}}_1 \|_q +  \| \widecheck{{\mathbf{A}}} - \widecheck{{\mathbf{A}}}_1 \|_q  \right) \geq \frac{1}{2} \|\widebar{{\mathbf{A}}}_1 - \widebar{{\mathbf{A}}}_2\|_q = 2^{1/q-1}\xi.
	\end{split}
\end{equation*}
\end{proof}
Combining Theorems \ref{th: low rank matrix reconstruction} and \ref{th: matrix reconstruction lower bound}, we conclude that the truncated SVD $\widehat{\mathbf{A}}$ achieves the optimal rate of low-rank matrix estimation error among all possible procedures $\widecheck{{\mathbf{A}}}$ in the class of $\mathcal{F}_r(\xi)$.

\section{Subspace perturbation bounds}\label{sec:wedin}
In this section, we apply the perturbation projection error bound established in Theorem \ref{th:SVD-projection} to derive a user-friendly subspace (singular vectors) perturbation bound.
\begin{Theorem}\label{th: variant 2 of Wedin} Consider the same perturbation setting as in Theorem \ref{th: low rank matrix reconstruction}. For any $q \geq 1$, we have
		\begin{equation*}
		\max\left\{\|\sin \Theta(\widehat{{\mathbf{U}}}, {\mathbf{U}})\|_q, \|\sin \Theta(\widehat{{\mathbf{V}}}, {\mathbf{V}})\|_q\right\} \leq \frac{2\| {\mathbf{Z}}_{\max(r)} \|_q }{\sigma_r({\mathbf{A}})}.
	\end{equation*}
\end{Theorem}
\begin{proof}
By Theorem \ref{th:SVD-projection}, we have
\begin{equation*}
	\| P_{\widehat{{\mathbf{U}}}_\perp} {\mathbf{A}} \|_q \leq 2 \| {\mathbf{Z}}_{\max(r)} \|_q.
\end{equation*}
Since the left singular subspace of ${\mathbf{A}}$ is ${\mathbf{U}}$, we have ${\mathbf{U}}\U^\top{\mathbf{A}} = P_{{\mathbf{U}}} {\mathbf{A}} = {\mathbf{A}}$. Then
\begin{equation*}
	\|\sin \Theta(\widehat{{\mathbf{U}}}, {\mathbf{U}})\|_q = \| \widehat{{\mathbf{U}}}_\perp^\top {\mathbf{U}} \|_q \overset{\text{Lemma } \ref{lm: singular value characterization} }\leq \frac{\| \widehat{{\mathbf{U}}}_\perp^\top{\mathbf{U}}\U^\top{\mathbf{A}} \|_q}{\sigma_r({\mathbf{U}}^\top{\mathbf{A}})} = \frac{\|P_{\widehat{\mathbf{U}}_\perp}{\mathbf{A}}\|_q}{\sigma_r({\mathbf{A}})} \leq \frac{2 \| {\mathbf{Z}}_{\max(r)} \|_q}{\sigma_r({\mathbf{A}})}.
\end{equation*}
\end{proof}
We note that several similar bounds are developed towards the applications in statistics and machine learning in the past few years, for example, \cite[Corollary 4.1]{vu2013minimax}, \cite[Theorem 2]{yu2014useful}, and \cite[Lemma 5.1]{lei2015consistency}. When the matrix is positive semidefinite, these results yield
\begin{equation}\label{ineq:vu}
\begin{split}
& \left\|\sin\Theta(\widehat{\mathbf{U}}, {\mathbf{U}})\right\|_F \leq \frac{\sqrt{2}\|{\mathbf{Z}}\|_F}{\sigma_r({\mathbf{A}})}, \quad \text{(\cite[Corollary 4.1]{vu2013minimax})},
\end{split}
\end{equation}
\begin{equation}\label{ineq:yu-lei}
\begin{split}
& \left\|\sin\Theta(\widehat{\mathbf{U}}, {\mathbf{U}})\right\|_F \leq \frac{2\min\{r^{1/2}\|{\mathbf{Z}}\|, \|{\mathbf{Z}}\|_F\}}{\sigma_r({\mathbf{A}})} \quad \text{\cite[Theorem 2]{yu2014useful}, \cite[Lemma 5.1]{lei2015consistency}}.
\end{split}
\end{equation}
When ${\mathbf{A}}, {\mathbf{Z}}, {\mathbf{B}}$ are asymmetric, \cite{yu2014useful} also proved
\begin{equation}\label{ineq:yu}
    \begin{split}
        \left\|\sin\Theta(\widehat{\mathbf{U}}, {\mathbf{U}})\right\|_F \leq \frac{2(2\|{\mathbf{A}}\| + \|{\mathbf{Z}}\|)\min\{r^{1/2}\|{\mathbf{Z}}\|, \|{\mathbf{Z}}\|_F\}}{\sigma_r^2({\mathbf{A}})} \quad \text{\cite[Theorem 3]{yu2014useful}}.
    \end{split}
\end{equation}
The perturbation bounds \eqref{ineq:vu}\eqref{ineq:yu-lei}\eqref{ineq:yu}, along with Theorem \ref{th: variant 2 of Wedin} in this paper, are ``user friendly" as they do not involve $\widehat{\mathbf{U}}$, $\widehat{\mathbf{V}}$ or ${\mathbf{B}}$ in contrast to the classical Wedin's $\sin\Theta$ bound \eqref{ineq:wedin-perturbation}. This advantage facilitates the application of these perturbations to many settings when ${\mathbf{A}}$ and ${\mathbf{Z}}$ are the given arguments: one no longer needs to further bound $\|{\mathbf{Z}}\widehat{{\mathbf{V}}}\|_q$, $\|\widehat{\mathbf{U}}^\top{\mathbf{Z}}\|_q$. The ``user friendly" advantage is also important in many settings as the denominator of \eqref{ineq:wedin-perturbation}, $\sigma_r({\mathbf{B}})$, depends highly on the perturbation ${\mathbf{Z}}$ and can be rather small due to perturbation \cite{yu2014useful}. In addition, our new result in Theorem \ref{th: variant 2 of Wedin} has a better dependence on both ${\mathbf{Z}}$ and $\sigma_r({\mathbf{A}})$ than \eqref{ineq:vu}\eqref{ineq:yu-lei}\eqref{ineq:yu} because
$$\|{\mathbf{Z}}_{\max(r)}\|_F \leq \min\left\{r^{1/2} \|{\mathbf{Z}}\|, \|{\mathbf{Z}}\|_F\right\},$$
while the opposite side of this inequality does not hold. Moreover, Theorem \ref{th: variant 2 of Wedin} covers the more general asymmetric matrices in Schatten-$q$ sin$\Theta$ norms for any $q \in [1, \infty]$.

\section{Simulations} \label{sec: numerical study}

In this section, we provide numerical studies to support our theoretical results. We specifically compare the low-rank matrix estimation error bound (Theorem \ref{th: low rank matrix reconstruction}) and the matrix perturbation projection error bound (Theorem \ref{th:SVD-projection}) in Section \ref{sec:main-result} with the results in previous literature. In each setting, we randomly generate a perturbation ${\mathbf{Z}}  = \u \v^\top + \widetilde{{\mathbf{Z}}}$, draw ${\mathbf{A}}$ by a to-be-specified scheme, and construct ${\mathbf{B}} = {\mathbf{A}} + {\mathbf{Z}}$. Here $\u, \v$ are randomly generated unit vectors and $\widetilde{{\mathbf{Z}}}$ has i.i.d. $N(0, \sigma^2)$ entries. Throughout the simulation studies, we consider the Schatten-$2$ norm (i.e., Frobenius norm) as the error metric. Each simulation setting is repeated for 100 times and the average values are reported.

\subsection{Numerical Comparison of Low-Rank Matrix Estimation Error Bounds} \label{sec: numerical matrix reconstruction}
We first compare the low-rank matrix estimation error bound $\|\widehat{\mathbf{A}} - {\mathbf{A}}\|_q$ in Theorem \ref{th: low rank matrix reconstruction} and the bounds in \eqref{ineq: matrix reconstruction via q-norm} and \eqref{ineq: matrix reconstruction via spectral norm}. We set $n \in \{100,300\}, r \in \{4,6,\ldots, 16\}$, $\sigma = 0.02$, and generate ${\mathbf{A}} = {\mathbf{U}} \boldsymbol{\Sigma}_1 {\mathbf{V}}^\top$, where ${\mathbf{U}} \in \mathbb{R}^{n \times r}, {\mathbf{V}} \in \mathbb{R}^{n \times r}$ are independently drawn from $\mathbb{O}_{n,r}$ uniformly at random; $\boldsymbol{\Sigma}_1$ is a diagonal matrix with singular values decaying polynomially as: $(\boldsymbol{\Sigma}_1)_{[i,i]} = \frac{10}{i}$, $1 \leq i \leq r$.

 The evaluations of the upper bounds in Theorem \ref{th: low rank matrix reconstruction}, \eqref{ineq: matrix reconstruction via q-norm}, \eqref{ineq: matrix reconstruction via spectral norm}, and the true value of $\|\widehat{{\mathbf{A}}} - {\mathbf{A}}\|_F$ are given in Figure \ref{fig: simulation2}. It shows that the upper bound in Theorem \ref{th: low rank matrix reconstruction} is tighter than the upper bounds in \eqref{ineq: matrix reconstruction via q-norm}, \eqref{ineq: matrix reconstruction via spectral norm} in all settings. In addition, when $n$ increases from $100$ to $300$, the upper bound of \eqref{ineq: matrix reconstruction via q-norm} significantly increases while the upper bound of Theorem \ref{th: low rank matrix reconstruction} remains steady. This is because the upper bounds of \eqref{ineq: matrix reconstruction via q-norm} and Theorem \ref{th: low rank matrix reconstruction} rely on $\|{\mathbf{Z}}\|_F$ and $\|{\mathbf{Z}}_{\max(r)}\|_F$, respectively.
\begin{figure}
	\centering
	\subfigure[$n = 100$]{\includegraphics[height = 0.3\textwidth]{matrix_reconstruction_poly_decay_p100.pdf}}
	\hskip1cm
	\subfigure[$n = 300$]{\includegraphics[height = 0.3\textwidth]{matrix_reconstruction_poly_decay_p300.pdf}}
	\caption{Low-rank matrix estimation error bound (Theorem \ref{th: low rank matrix reconstruction}), upper bounds \eqref{ineq: matrix reconstruction via q-norm}, \eqref{ineq: matrix reconstruction via spectral norm} and the true value of $\|\widehat{{\mathbf{A}}} - {\mathbf{A}}\|_F$
	} \label{fig: simulation2}
\end{figure}

\subsection{Numerical Comparison of Matrix Perturbation Projection Error Bounds} \label{sec: numerical matrix perturbation projection}

Next, we compare the matrix perturbation projection error bound in Theorem \ref{th:SVD-projection} with the upper bound \eqref{ineq: matrix projection bound via sin Theta} derived from Wedin's sin$\Theta$ Theorem. We generate ${\mathbf{B}}, {\mathbf{Z}}$ in the same way as the previous simulation setting. When generating $\boldsymbol{\Sigma}_1$ in ${\mathbf{A}}$, apart from the polynomial singular value decaying pattern considered in the last setting, we also consider the following exponential singular value decaying pattern: $(\boldsymbol{\Sigma}_1)_{[i,i]} = 2^{5-i}$, $1 \leq i \leq r$.

 The values of the upper bounds in Theorem \ref{th:SVD-projection} and \eqref{ineq: matrix projection bound via sin Theta}, along with the true value of $\|P_{\widehat{{\mathbf{U}}}_\perp}{\mathbf{A}}\|_q$, are presented in Figure \ref{fig: simulation1}. We find the bound of Theorem \ref{th:SVD-projection} is much tighter than the bound in \eqref{ineq: matrix projection bound via sin Theta}. As $r$ increases or singular value decaying pattern becomes exponential, i.e., ${\mathbf{A}}$ becomes ill-conditioned, \eqref{ineq: matrix projection bound via sin Theta} becomes loose while Theorem \ref{th:SVD-projection} can still be sharp.
\begin{figure}
	\centering
	\subfigure[Singular values of ${\mathbf{A}}$ decay polynomially]{\includegraphics[height = 0.3\textwidth]{matrix_projection_poly_decay.pdf}}
	\hskip1cm
	\subfigure[Singular values of ${\mathbf{A}}$ decay exponentially]{\includegraphics[height = 0.3\textwidth]{matrix_projection_expdecay.pdf}}
	\caption{Matrix perturbation projection error upper bound (Theorem \ref{th:SVD-projection}), upper bound via Wedin's sin$\Theta$ Theorem \eqref{ineq: matrix projection bound via sin Theta}, and the true value of $\|P_{\widehat{\mathbf{U}}_\perp}{\mathbf{A}}\|_F$.
	} \label{fig: simulation1}
\end{figure}

\section{Discussions} \label{sec: conclusion}

In this paper, we prove a sharp upper bound for estimation error of rank-$r$ truncated SVD ($\|\widehat{\mathbf{A}}- {\mathbf{A}}\|_q$) under perturbation, and show its optimality in low-rank matrix estimation. The key technical tool we use is a novel matrix perturbation projection error bound for $\|P_{\widehat{{\mathbf{U}}}_\perp} {\mathbf{A}}\|_q$. As a byproduct, we also provide a sharper user-friendly sin$\Theta$ perturbation bound. The numerical studies demonstrate the advantages of these new results over the ones in the literature.

Throughout the paper, we study the additive perturbations and it is a future work to extend the results to multiplicative perturbations \cite{li1998relative,li1998relative2}. Also for convenience of presentation, we focus on the real number field in this paper. It is interesting to extend the developed results to the field of complex numbers. The main technical work for such an extension includes a dual representation of the truncated Schatten-$q$ norm in the field of complex numbers, i.e., a complex version of Lemma \ref{lm: charac of Schatten-q norm}.

Apart from the widely studied perturbation theory on singular value decomposition, the perturbation theory for other problems, such as pseudo-inverses \cite{wedin1973perturbation,stewart1977perturbation}, least squares problems \cite{stewart1977perturbation}, orthogonal projection \cite{stewart1977perturbation,xu2020perturbation,fierro1996perturbation,chen2016perturbation}, rank-one perturbation \cite{zhu2019rank}, are also important topics. It would be interesting to explore whether the tools developed in this paper is useful in studying the perturbation theory for these problems.

\section{Additional Lemmas and Proofs}\label{sec:additional-proof}

\begin{proof}[Proof of Lemma \ref{lem: triangle of trun schatten q}]
Since $\|{\mathbf{A}}_{\max(r)}\|_q = (\sum_{i=1}^r \sigma_i^q({\mathbf{A}}))^{1/q}$, we have $\|{\mathbf{A}}_{\max(r)}\|_q \geq 0$,
\begin{equation*}
    \|{\mathbf{A}}_{\max(r)}\|_q = 0 \text{ if and only if } \sigma_1({\mathbf{A}}) = 0 \text{ if and only if }{\mathbf{A}} = 0.
\end{equation*}
Since $\sigma_i(\lambda{\mathbf{A}}) = |\lambda|\sigma_i({\mathbf{A}})$, we have $\|(\lambda{\mathbf{A}})_{\max(r)}\|_q = |\lambda|\cdot \|{\mathbf{A}}_{\max(r)}\|_q$.
Next, we apply Lemma \ref{lm: charac of Schatten-q norm} to prove the triangle inequality:
\begin{equation*}
\begin{split}
		& \|({\mathbf{A}} + {\mathbf{B}})_{\max(r)}\|_q \overset{\text{Lemma \ref{lm: charac of Schatten-q norm}}}{=} \sup_{\|{\mathbf{X}} \|_p \leq 1, {\rm rank}({\mathbf{X}}) \leq r} \left\langle {\mathbf{A}} + {\mathbf{B}}, {\mathbf{X}} \right \rangle\\
		\leq & \sup_{\|{\mathbf{X}} \|_p \leq 1, {\rm rank}({\mathbf{X}}) \leq r} \left\langle {\mathbf{A}} , {\mathbf{X}} \right \rangle + \sup_{\|{\mathbf{X}} \|_p \leq 1, {\rm rank}({\mathbf{X}}) \leq r} \left\langle {\mathbf{B}}, {\mathbf{X}} \right \rangle
		\overset{\text{Lemma \ref{lm: charac of Schatten-q norm}}}{=} \|{\mathbf{A}}_{\max(r)}\|_q + \|{\mathbf{B}}_{\max(r)}\|_q.
\end{split}
\end{equation*}
Finally for any orthogonal matrices ${\mathbf{U}}$ and ${\mathbf{V}}$, since $\sigma_i({\mathbf{A}}) = \sigma_i({\mathbf{U}}{\mathbf{A}}{\mathbf{V}})$, we have $\|{\mathbf{A}}_{\max(r)}\|_q = \|{\mathbf{U}}{\mathbf{A}}_{\max(r)}{\mathbf{V}}\|_q$.
\end{proof}

\begin{proof}[Proof of Lemma \ref{lm: optimality of SVD in truncated Schatten-q norm}]
By the well-known Eckart-Young-Mirsky Theorem \cite{eckart1936approximation,mirsky1960symmetric,golub1987generalization}, the truncated SVD achieves the best low-rank matrix approximation in any unitarily invariant norm. This lemma follows from the Eckart-Young-Mirsky Theorem and the fact that $\|(\cdot)_{\max(k)}\|_q$ is a unitarily invariant matrix norm (Lemma \ref{lem: triangle of trun schatten q}).
\end{proof}

\begin{Lemma}[Properties of $\sin\Theta({\mathbf{U}}_1, {\mathbf{U}}_2)$]\label{lm: spectral of sin theta}
    Suppose ${\mathbf{U}}_1,{\mathbf{U}}_2,{\mathbf{U}}_3 \in \mathbb{O}_{p,r}$ are $p \times r\, (r \leq p)$ matrices with orthonormal columns.
    \begin{itemize}[leftmargin=*]
    \item (Spectrum of $\sin\Theta({\mathbf{U}}_1, {\mathbf{U}}_2)$) ${\mathbf{U}}_{1 \perp}^\top {\mathbf{U}}_2$ and $\sin \Theta({\mathbf{U}}_1, {\mathbf{U}}_2)$ share the same singular values, i.e.,
    \begin{equation} \label{eq: spectral equality}
        \sigma_i({\mathbf{U}}_{1 \perp}^\top {\mathbf{U}}_2) = \sigma_i(\sin \Theta({\mathbf{U}}_1, {\mathbf{U}}_2)), \quad i = 1, \ldots, r.
    \end{equation}
    In particular, $\| {\mathbf{U}}_{1 \perp}^\top {\mathbf{U}}_2\|_q = \left\| \sin \Theta({\mathbf{U}}_1, {\mathbf{U}}_2) \right\|_q$ for any $q \in [1,\infty]$.
    \item (Triangle Inequality)
        $$\|\sin\Theta({\mathbf{U}}_1, {\mathbf{U}}_2)\|_q \leq \|\sin\Theta({\mathbf{U}}_1, {\mathbf{U}}_3)\|_q + \|\sin\Theta({\mathbf{U}}_2, {\mathbf{U}}_3)\|_q $$
        \item (Equivalence to other distances) The Schatten-$q$ $\sin\Theta$ distance defined as \eqref{label:Schatten-q-distance} is equivalent to other metrics, as the following inequality holds,
        \begin{equation*}
       \|\sin\Theta({\mathbf{U}}_1, {\mathbf{U}}_2)\|_q \leq \inf_{\mathbf{O}\in \mathbb{O}_r} \|{\mathbf{U}}_1 - {\mathbf{U}}_2\mathbf{O}\|_q \leq 2 \|\sin\Theta({\mathbf{U}}_1, {\mathbf{U}}_2)\|_q;
        \end{equation*}
        \begin{equation*}
        \|\sin\Theta({\mathbf{U}}_1, {\mathbf{U}}_2)\|_q \leq \|{\mathbf{U}}_1{\mathbf{U}}_1^\top - {\mathbf{U}}_2{\mathbf{U}}_2^\top\|_q \leq 4 \|\sin\Theta({\mathbf{U}}_1, {\mathbf{U}}_2)\|_q.
        \end{equation*}
    \end{itemize}
\end{Lemma}
\begin{proof}
\begin{itemize}[leftmargin=*]
\item {\bf (Spectrum of $\sin\Theta({\mathbf{U}}_1, {\mathbf{U}}_2)$)}. Suppose ${\mathbf{U}}_{1 \perp}^\top {\mathbf{U}}_2$ has singular value decomposition ${\mathbf{W}}_1 \boldsymbol{\Sigma} {\mathbf{V}}_1^\top$ and ${\mathbf{U}}_1^\top {\mathbf{U}}_2$ has singular value decomposition ${\mathbf{W}}_2 \boldsymbol{\Lambda} {\mathbf{V}}_2^\top$, where ${\mathbf{W}}_1 \in \mathbb{R}^{(p-r) \times r}; {\mathbf{W}}_2, \boldsymbol{\Sigma}, \boldsymbol{\Lambda}, {\mathbf{V}}_1, {\mathbf{V}}_2 \in \mathbb{R}^{r \times r}$. By the definition of $\sin \Theta$ distance, $\sigma_i \left(\sin \Theta({\mathbf{U}}_1, {\mathbf{U}}_2)  \right) = \sqrt{ 1- \boldsymbol{\Lambda}^2_{[r-i,r-i]}}$. So to show the result of \eqref{eq: spectral equality}, we only need to show
\begin{equation} \label{eq: relationship of bLemaba and bSigma}
    \sqrt{1- \boldsymbol{\Lambda}^2_{[r-i,r-i]}} = \boldsymbol{\Sigma}_{[i, i]}.
\end{equation}
Since ${\mathbf{V}}_1, {\mathbf{V}}_2$ are both orthogonal matrices, suppose ${\mathbf{V}}_1 {\mathbf{R}} = {\mathbf{V}}_2$ where ${\mathbf{R}}$ is a $r \times r$ orthogonal matrix. Then
\begin{equation*}
\begin{split}
    {\mathbf{I}} & = {\mathbf{U}}_2^\top {\mathbf{U}}_{1\perp}{\mathbf{U}}_{1\perp}^\top {\mathbf{U}}_2 + {\mathbf{U}}_2^\top {\mathbf{U}}_{1}{\mathbf{U}}_{1}^\top {\mathbf{U}}_2 \\
     & = {\mathbf{V}}_1 \boldsymbol{\Sigma}^2 {\mathbf{V}}_1^\top + {\mathbf{V}}_2 \boldsymbol{\Lambda}^2 {\mathbf{V}}_2^\top = {\mathbf{V}}_1 \left( \boldsymbol{\Sigma}^2 + {\mathbf{R}} \boldsymbol{\Lambda}^2 {\mathbf{R}}^\top\right) {\mathbf{V}}_1^\top.
\end{split}
\end{equation*}
So $\boldsymbol{\Sigma}^2 + {\mathbf{R}} \boldsymbol{\Lambda}^2 {\mathbf{R}}^\top = {\mathbf{I}}$, and this means that ${\mathbf{R}}$ could only be a permutation matrix. And since $\boldsymbol{\Sigma}_{[1,1]} \geq \ldots \geq \boldsymbol{\Sigma}_{[r,r]}$ and $\boldsymbol{\Lambda}_{[1,1]} \geq \ldots \geq \boldsymbol{\Lambda}_{[r,r]}$, the only way that can make $\boldsymbol{\Sigma}^2 + {\mathbf{R}} \boldsymbol{\Lambda}^2 {\mathbf{R}}^\top = {\mathbf{I}}$ to be true for a permutation matrix ${\mathbf{R}}$ is
\begin{equation*}
     \boldsymbol{\Lambda}^2_{[r-i,r-i]} +  \boldsymbol{\Sigma}^2_{[i, i]} = 1.
\end{equation*}
This has finished the proof for $\sigma_i({\mathbf{U}}_{1\perp}^\top {\mathbf{U}}_2) = \sigma_i(\sin\Theta({\mathbf{U}}_1, {\mathbf{U}}_2))$ for any $i=1,\ldots, r$. Thus, $\|{\mathbf{U}}_{1\perp}^\top{\mathbf{U}}_2\|_q = \|\sin\Theta({\mathbf{U}}_1,{\mathbf{U}}_2)\|_q$ for any $q\in [1,\infty]$.

\item {\bf (Triangle Inequality)}.
\begin{equation*}
    \begin{split}
        \|\sin\Theta({\mathbf{U}}_1, {\mathbf{U}}_2)\|_q & \overset{(a)}= \| {\mathbf{U}}_{1\perp}^\top {\mathbf{U}}_2 \|_q  = \| {\mathbf{U}}_{1\perp}^\top (P_{{\mathbf{U}}_3} + P_{{\mathbf{U}}_{3\perp}}) {\mathbf{U}}_2 \|_q \\
        & \overset{(b)}\leq \| {\mathbf{U}}_{1\perp}^\top P_{{\mathbf{U}}_3} {\mathbf{U}}_2 \|_q + \| {\mathbf{U}}_{1\perp}^\top P_{{\mathbf{U}}_{3\perp}} {\mathbf{U}}_2  \|_q \\
        & \leq \| {\mathbf{U}}_{1\perp} {\mathbf{U}}_3 \|_q \| {\mathbf{U}}_3^\top {\mathbf{U}}_2 \| + \| {\mathbf{U}}_{1\perp}^\top {\mathbf{U}}_{3\perp} \| \| {\mathbf{U}}_{3\perp}^\top {\mathbf{U}}_2  \|_q \\
        & \overset{(c)} \leq \| {\mathbf{U}}_{1\perp} {\mathbf{U}}_3 \|_q + \| {\mathbf{U}}_{3\perp}^\top {\mathbf{U}}_2  \|_q\\
        & = \|\sin\Theta({\mathbf{U}}_1, {\mathbf{U}}_3)\|_q + \|\sin\Theta({\mathbf{U}}_3, {\mathbf{U}}_2)\|_q.
    \end{split}
\end{equation*}
Here, (a) is due to \eqref{eq: spectral equality}, (b) is a triangle inequality, (c) is due to $ \| {\mathbf{U}}_{1\perp}^\top {\mathbf{U}}_{3\perp}\| \leq 1, \| {\mathbf{U}}_3^\top {\mathbf{U}}_2 \| \leq 1$.

\item {\bf (Equivalence to other distances)}.
Since all metrics mentioned in Lemma \ref{lm: spectral of sin theta} is rotation invariant, i.e. for any $\mathbf{O} \in \mathbb{O}_{p}$, $\sin \Theta ({\mathbf{U}}_1, {\mathbf{U}}_2) = \sin \Theta(\mathbf{O} {\mathbf{U}}_1, \mathbf{O}{\mathbf{U}}_2)$, without loss of generality, we can assume
\begin{equation*}
    {\mathbf{U}}_2 = \left[ \begin{array}{c}
         {\mathbf{I}}_r  \\
         {\mathbf{0}}_{(p-r) \times r}
    \end{array}  \right].
\end{equation*} In this case
\begin{equation*}
\begin{split}
    \inf_{\mathbf{O}\in \mathbb{O}_r} \|{\mathbf{U}}_1 - {\mathbf{U}}_2\mathbf{O}\|_q & = \inf_{\mathbf{O}\in \mathbb{O}_r} \left\| \begin{array}{c}
         ({\mathbf{U}}_1)_{[1:r,:]} - \mathbf{O} \\
         ({\mathbf{U}}_1)_{[(r+1):p,:]}
    \end{array}  \right\|_q \\
    & \overset{(a)}= \inf_{\mathbf{O}\in \mathbb{O}_r} \sup_{\|{\mathbf{X}}\|_p \leq 1} \left\langle\begin{array}{c}
         ({\mathbf{U}}_1)_{[1:r,:]} -\mathbf{O}  \\
         ({\mathbf{U}}_1)_{[(r+1):p,:]}
    \end{array}, {\mathbf{X}}  \right\rangle \\
    & \geq \sup_{\|{\mathbf{X}}\|_p \leq 1} \left\langle
         ({\mathbf{U}}_1)_{[(r+1):p,:]} , {\mathbf{X}}_{[(r+1):p,:]}  \right\rangle\\
    & \overset{(b)}= \|({\mathbf{U}}_1)_{[(r+1):p,:]} \|_q = \|{\mathbf{U}}_{2\perp}^\top {\mathbf{U}}_1 \|_q = \|\sin\Theta({\mathbf{U}}_1, {\mathbf{U}}_2)\|_q.
\end{split}
\end{equation*}
Here, (a)(b) are due to Lemma \ref{lm: charac of Schatten-q norm}.

Now we prove the upper bound of $\inf_{\mathbf{O}\in \mathbb{O}_r} \|{\mathbf{U}}_1 - {\mathbf{U}}_2\mathbf{O}\|_q$. Recall ${\mathbf{U}}_1^\top {\mathbf{U}}_2$ has singular value decomposition ${\mathbf{W}}_2 \boldsymbol{\Lambda} {\mathbf{V}}_2^\top$. Then
\begin{equation*}
\begin{split}
    \inf_{\mathbf{O}\in \mathbb{O}_r} \|{\mathbf{U}}_1 - {\mathbf{U}}_2\mathbf{O}\|_q & \leq \|{\mathbf{U}}_1 - {\mathbf{U}}_2 {\mathbf{W}}_2 {\mathbf{V}}_2^\top  \|_q  \\
    & \leq \| P_{{\mathbf{U}}_2} ({\mathbf{U}}_1 - {\mathbf{U}}_2 {\mathbf{W}}_2 {\mathbf{V}}_2^\top)  \|_q + \| P_{{\mathbf{U}}_{2\perp}} ({\mathbf{U}}_1 - {\mathbf{U}}_2 {\mathbf{W}}_2 {\mathbf{V}}_2^\top)  \|_q \\
     & \leq \| {\mathbf{W}}_2 ({\mathbf{I}}_r - \boldsymbol{\Lambda}) {\mathbf{V}}_2^\top \|_q +  \|{\mathbf{U}}_{2\perp}^\top {\mathbf{U}}_1\|_q \\
     & = \left( \sum_{i=1}^r (1 - \boldsymbol{\Lambda}_{[i,i]})^q \right)^{1/q} + \|{\mathbf{U}}_{2\perp}^\top {\mathbf{U}}_1\|_q\\
     & \leq \left( \sum_{i=1}^r \left(\sqrt{1 - \boldsymbol{\Lambda}^2_{[i,i]}}\right)^q \right)^{1/q} + \|{\mathbf{U}}_{2\perp}^\top {\mathbf{U}}_1\|_q \\
     & \overset{(a)}\leq 2 \|\sin\Theta({\mathbf{U}}_1, {\mathbf{U}}_2)\|_q.
\end{split}
\end{equation*}
Here, (a) is due the relationship between the singular values of ${\mathbf{U}}_{2\perp}^\top {\mathbf{U}}_1$ and ${\mathbf{U}}_2^\top {\mathbf{U}}_1$ established in \eqref{eq: relationship of bLemaba and bSigma}.

Finally, we prove the equivalency of $\|\sin\Theta({\mathbf{U}}_1, {\mathbf{U}}_2)\|_q$ and $\|{\mathbf{U}}_1{\mathbf{U}}_1^\top - {\mathbf{U}}_2{\mathbf{U}}_2^\top\|_q$. First
\begin{equation*}
    \|{\mathbf{U}}_1{\mathbf{U}}_1^\top - {\mathbf{U}}_2{\mathbf{U}}_2^\top\|_q \geq \| {\mathbf{U}}_{2\perp} ( {\mathbf{U}}_1{\mathbf{U}}_1^\top - {\mathbf{U}}_2{\mathbf{U}}_2^\top ) \|_q =  \|{\mathbf{U}}_{2\perp}^\top {\mathbf{U}}_1\|_q  = \|\sin\Theta({\mathbf{U}}_1, {\mathbf{U}}_2)\|_q.
\end{equation*}
On the other hand, notice the decomposition
\begin{equation*}
\begin{split}
        {\mathbf{U}}_1{\mathbf{U}}_1^\top - {\mathbf{U}}_2{\mathbf{U}}_2^\top & = (P_{{\mathbf{U}}_2} + P_{{\mathbf{U}}_{2\perp}}) {\mathbf{U}}_1{\mathbf{U}}_1^\top  (P_{{\mathbf{U}}_2} + P_{{\mathbf{U}}_{2\perp}})- {\mathbf{U}}_2{\mathbf{U}}_2^\top\\
        & =  {\mathbf{U}}_2 \left( ({\mathbf{U}}_2^\top {\mathbf{U}}_1 ) ({\mathbf{U}}_2^\top {\mathbf{U}}_1 )^\top - {\mathbf{I}}_r  \right) {\mathbf{U}}_2^\top + P_{{\mathbf{U}}_{2\perp}} {\mathbf{U}}_1{\mathbf{U}}_1^\top P_{{\mathbf{U}}_2} \\
        & \quad + P_{{\mathbf{U}}_2}  {\mathbf{U}}_1{\mathbf{U}}_1^\top P_{{\mathbf{U}}_{2\perp}} + P_{{\mathbf{U}}_{2\perp}} {\mathbf{U}}_1{\mathbf{U}}_1^\top P_{{\mathbf{U}}_{2\perp}}.
\end{split}
\end{equation*}
So,
\begin{equation*}
    \begin{split}
        \|{\mathbf{U}}_1{\mathbf{U}}_1^\top - {\mathbf{U}}_2{\mathbf{U}}_2^\top\|_q & \overset{(a)}\leq \|({\mathbf{U}}_2^\top {\mathbf{U}}_1 ) ({\mathbf{U}}_2^\top {\mathbf{U}}_1 )^\top - {\mathbf{I}}_r  \|_q + 3\|{\mathbf{U}}_{2\perp}^\top {\mathbf{U}}_1 \|_q \\
        & \leq \|{\mathbf{I}}_r - \boldsymbol{\Lambda}^2 \|_q +  3\|{\mathbf{U}}_{2\perp}^\top {\mathbf{U}}_1 \|_q\\
        & = \left( \sum_{i=1}^r \left(1 - \boldsymbol{\Lambda}^2_{[i,i]}\right)^q \right)^{1/q} + 3\|{\mathbf{U}}_{2\perp}^\top {\mathbf{U}}_1\|_q\\
        & \leq \left( \sum_{i=1}^r \left(\sqrt{1 - \boldsymbol{\Lambda}^2_{[i,i]}}\right)^q \right)^{1/q} + 3\|{\mathbf{U}}_{2\perp}^\top {\mathbf{U}}_1\|_q \\
        & \overset{(b)}= 4 \|\sin\Theta({\mathbf{U}}_1, {\mathbf{U}}_2)\|_q.
    \end{split}
\end{equation*}
Here, (a) is due to triangle inequality and $\|{\mathbf{U}}_2^\top {\mathbf{U}}_1\| \leq 1$, (b) is due to \eqref{eq: spectral equality} and \eqref{eq: relationship of bLemaba and bSigma}.
\end{itemize}
\end{proof}

The following Lemma \ref{lm: singular value characterization} characterizes the singular values of the product of matrices.
\begin{Lemma}[Singular values of the product of two matrices] \label{lm: singular value characterization}
    Suppose ${\mathbf{A}}\in \mathbb{R}^{m \times n}$, ${\mathbf{B}} \in \mathbb{R}^{n \times b}$. Then
    \begin{equation}\label{ineq: singular value bound}
        \sigma_i({\mathbf{A}} {\mathbf{B}}) \leq \sigma_i({\mathbf{A}}) \|{\mathbf{B}}\|, \quad \sigma_i({\mathbf{A}} {\mathbf{B}}) \geq \sigma_i({\mathbf{A}}) \sigma_n({\mathbf{B}}),
    \end{equation}
    \begin{equation} \label{ineq: shatten q norm bound}
        \|{\mathbf{A}}{\mathbf{B}}\|_q \leq \|{\mathbf{A}}\|_q \|{\mathbf{B}}\|, \quad  \|{\mathbf{A}}{\mathbf{B}}\|_q \geq \|{\mathbf{A}}\|_q \sigma_n({\mathbf{B}})
    \end{equation}
    for any $1 \leq i \leq m \wedge n$ and $q \geq 1$.
\end{Lemma}

\begin{proof} First
\begin{equation*}
\begin{split}
        \sigma_i({\mathbf{A}} {\mathbf{B}})  = \lambda_i^{1/2}({\mathbf{A}} {\mathbf{B}} {\mathbf{B}}^\top {\mathbf{A}}^\top) = \lambda_i^{1/2}({\mathbf{B}} {\mathbf{B}}^\top {\mathbf{A}}^\top {\mathbf{A}})  &\overset{(a)} \geq (\lambda_i({\mathbf{A}}^\top {\mathbf{A}}) \lambda_{n-i+1}({\mathbf{B}} {\mathbf{B}}^\top) )^{1/2} \\
        & \geq \sigma_i({\mathbf{A}}) \sigma_n({\mathbf{B}}).
\end{split}
\end{equation*}
Here (a) is due to \cite[P.371 Theorem H.1.d.]{marshall1979inequalities}.
Next we show $\sigma_i({\mathbf{A}}{\mathbf{B}})\leq \sigma_i({\mathbf{A}})\|{\mathbf{B}}\|$. Recall the best low-rank approximation property of SVD \cite{mirsky1960symmetric,golub1987generalization}, we have
\begin{equation*}
    \sigma_i({\mathbf{A}}) = \min_{{\mathbf{X}} \in \mathbb{R}^{m \times n}, {\rm rank}({\mathbf{X}}) \leq i-1} \| {\mathbf{A}} - {\mathbf{X}} \|.
\end{equation*}
So
\begin{equation*}
\begin{split}
    \sigma_i({\mathbf{A}} {\mathbf{B}}) & = \min_{{\mathbf{X}} \in \mathbb{R}^{m \times n}, {\rm rank}({\mathbf{X}}) \leq i-1} \| {\mathbf{A}}{\mathbf{B}} - {\mathbf{X}} \| \leq \left\| {\mathbf{A}}{\mathbf{B}} - \sum_{k=1}^{i-1} \sigma_k({\mathbf{A}}) \u_k \v_k^\top {\mathbf{B}} \right\| \\
     &= \left\| {\mathbf{A}}_{\max(-(i-1))} {\mathbf{B}}\right\| \leq \left\|{\mathbf{A}}_{\max(-(i-1))} \right\|\cdot \|{\mathbf{B}} \| = \sigma_i({\mathbf{A}}) \|{\mathbf{B}}\|.
\end{split}
\end{equation*}
Next,
$$\|{\mathbf{A}}{\mathbf{B}}\|_q=(\sum_i \sigma_i^q({\mathbf{A}}{\mathbf{B}}))^{1/q} \leq (\sum_i \sigma_i^q({\mathbf{A}})\|{\mathbf{B}}\|^q)^{1/q} = \|{\mathbf{A}}\|_q \|{\mathbf{B}}\|,$$
$$\|{\mathbf{A}}{\mathbf{B}}\|_q=(\sum_i \sigma_i^q({\mathbf{A}}{\mathbf{B}}))^{1/q} \geq (\sum_i \sigma_i^q({\mathbf{A}})\sigma^q_n({\mathbf{B}}))^{1/q} = \|{\mathbf{A}}\|_q \sigma_n({\mathbf{B}}).$$
\end{proof}
\bibliographystyle{alpha}