Minimax perturbation bounds of the low-rank matrix under Ky Fan norm

1.   Introduction

Singular value decomposition (SVD) has been widely used in statistics, machine learning, and applied mathematics. Perturbation bounds often play a critical role in the analysis of the SVD. To be more specific, let

where both $A$ and $E$ have the same size $d_1\times d_2,$ and $A$ is a signal matrix which we are interested in, while $E$ stands for a perturbation matrix. In this paper, suppose that $\hat{A}$ and $A$ have the following singular value decompositions,

where $r\leq {\rm rank}(A), \; d_1\wedge d_2$ stands for $\min\{d_1, d_2\}.$ The singular values $\sigma_i$ and $\hat{\sigma}_i$ are in the decreasing order. $U = [u_1, \ldots, u_r], \; \hat{U} = [\hat{u}_1, \ldots, \hat{u}_r]\in\mathbb{O}_{d_1, r}$ (the set of all $d_1\times r$ orthonormal columns and $\mathbb{O}_{d_1}$: = $\mathbb{O}_{d_1, d_1}$), and $V = [v_1, \ldots, v_r], \; \hat{V} = [\hat{v}_1, \ldots, \hat{v}_r]\in\mathbb{O}_{d_2, r}.$ Unlike compressed sensing ^[5] to reconstruct the original signal, our goal is to estimate the underlying low-rank matrix $A$ and its leading left and right singular matrices $U, V$.

The problems to estimate $U, V$ have been widely studied in the literature ^{[1,3,4,10,12]}. Among these results, Davis and Kahan ^[3], Wedin ^[12] established the fundamental methods for matrix perturbation theory; Vu ^[10], Wang ^[11] discussed the rotations of singular vectors after random perturbation; Cai and Zhang ^[1] studied the rate-optimal perturbation bounds for singular subspaces; Fan et al. ^[4] gave an eigenvector perturbation bound and the robust covariance estimation. In addition, Luo et al. ^[6] considered the perturbation bound under Schatten-$q$ norm. Till now, a few of the existing works focused on the perturbation analysis of the matrix $A$ itself. This paper will consider the estimation of rank-$r$ matrix $A$ under Ky Fan norm which extends the results of Luo et al.

For a given $k\in\{1, 2, \ldots, d_1\wedge d_2\}$, the Ky Fan norm $\|M\|_{(k)}$ of the matrix $M\in\mathbb{R}^{d_1\times d_2}$ is given by $\|M\|_{(k)} = \sum_{i = 1}^k\sigma_i(M)$. Clearly, $\|\cdot\|_{(k)}$ is a unitarily invariant norm.

In this paper, we consider the estimation of rank-$r$ matrix $A$ (i.e., ${\Sigma_r}_\bot = 0$) via rank-$r$ truncated SVD $\hat{A}_r: = \hat{U}\hat{\Sigma}_r \hat{V}^T$ of $\hat{A}$. It is widely known that $\hat{A}_r$ is the best rank-$r$ approximation of $\hat{A}$. Here and throughout, $A_l$ or $(A)_l$ denotes the best rank-$l$ approximation of the matrix $A$.

Firstly, we establish the following upper bound.

Theorem 1.1. Let the observation matrix $\hat{A} = A+E\in \mathbb{R}^{d_1\times d_2},$ where $A$ is an unknown rank-$r$ matrix and $E$ is the perturbation matrix. Then

where $E_r$ denotes the best rank-$r$ approximation of the matrix $E$.

Remark 1.1. According to Eckart-Young-Mirsky Theorem and $rank(A) = r$, we have $\|\hat{A}_r-\hat{A}\|_{(k)}\leq\|A-\hat{A}\|_{(k)}$. Therefore,

If $r\ll d_1\wedge d_2$, then $\|E_r\|_{(k)}$ can be much smaller than $\|E\|_{(k)}$ for any $k\gg r$.

Remark 1.2. If $k = d_1\wedge d_2$, both the Ky Fan norm and the Schatten-1 norm are equal to the nuclear norm; If $k = 1$, both the Ky Fan norm and the Schatten-$\infty$ norm are equal to the spectral norm. Otherwise, the two norms are not included each other. Therefore, our results can be regarded as a supplement to the existing results.

Before stating the lower bound, for any $t > 0$, we define the class of $(A, E)$ as

Here $A, E\in\mathbb{R}^{d_1\times d_2}$ and $k\in\{1, 2, \ldots, d_1\wedge d_2\}$.

Theorem 1.2. For the low-rank perturbation model $\hat{A} = A+E\in \mathbb{R}^{d_1\times d_2}$, if $r\leq \frac{1}{2}(d_1\wedge d_2)$, then for any estimator $\tilde{A}$ based on the observation matrix $A+E$,

where $k\in\{1, 2, \ldots, d_1\wedge d_2\}$.

Theorem 1.2 shows that the upper bound given in Theorem 1.1 is sharp for the rank-$r$ truncated singular value decomposition estimator $\hat{A}_r$.

The principle angle $\Theta(V_1, V_2)$ of the matrices $V_1, V_2\in\mathbb{O}_{d, r}$ means the diagonal matrix

with the singular values $\sigma_i: = \sigma_i(V_1^TV_2)$ of $V_1^TV_2$ satisfying $\sigma_1\geq \sigma_2\geq\cdots\geq\sigma_r\geq0$. When $r = 1$, $\Theta(V_1, V_2)$ coincides with the angle of two $d$ dimensional unit vectors. In this paper, the $\sin\Theta$ distance is used to measure the difference between $V_1$ and $V_2$. i.e.,

Indeed, although $\|\sin\Theta(V_1, V_2)\|$ defines a semi-metric on $\mathbb{O}_{d, r}$, it is also satisfied

and

following from ^[7].

As a byproduct of Theorem 1.1, we can derive the perturbation bounds for the leading singular subspaces $U$ and $V$ under Ky Fan norm $\sin\Theta$ distance. i.e.,

Furthermore, we also give the corresponding lower bounds to show the above upper bounds are sharp.

2.   Proofs

Firstly, let us introduce some lemmas in order to prove Theorem 1.1.

2.1.   Auxiliary lemmas

A function $\Phi:\mathbb{R}^d\rightarrow \mathbb{R}$ is called a symmetric gauge function (^[9]) if (1) ${\bf{x}}\neq 0\Longrightarrow \Phi({\bf{x}}) > 0;$ (2) $\Phi(\alpha{\bf{x}}) = |\alpha|\Phi({\bf{x}})$ for $\alpha\in\mathbb{R}$; (3) $\Phi({\bf{x}}+{\bf{y}})\leq\Phi({\bf{x}})+\Phi({\bf{y}})$ for any ${\bf{x}}, {\bf{y}}\in\mathbb{R}^d$, and (4) $\Phi(J{\bf{x}}_\pi) = \Phi({\bf{x}})$, where $J$ is any diagonal matrix whose diagonal elements are 1 or -1, and $\pi$ is any permutation with $1, \ldots, d.$

For ${\bf{x}}, {\bf{y}}\in\mathbb{R}^d$, define the function

It is easy to check $\Psi(\cdot)$ is also a symmetric gauge function. In general, $\Psi({\bf{y}})$ is usually called the dual symmetric gauge function of $\Phi({\bf{x}})$. In particular, for a matrix $A\in\mathbb{R}^{d_1\times d_2}$, we can define

where $\sigma_1, \ldots, \sigma_{d_1\wedge d_2}$ are the singular values of $A$, then the following lemma is Lemma 3.4 in ^[9].

Lemma 2.1. Let $A, B\in \mathbb{R}^{d_1\times d_2}$ and their singular values are $\sigma_1\geq\cdots\geq\sigma_{d_1\wedge d_2}\geq 0$, $\xi_1\geq\cdots\geq\xi_{d_1\wedge d_2}\geq 0$ respectively. Then

According to Lemma 2.1, we introduce a dual characterization lemma.

Lemma 2.2. Let $A\in\mathbb{R}^{d_1\times d_2}$, there exists a symmetric gauge function $\Psi_k(\cdot)$ such that

for $k\in\{1, 2, \ldots, d_1\wedge d_2\}.$ In special case, if ${\rm rank}(A)\leq r,$ then

Proof. For any $k\in\{1, 2, \ldots, d_1\wedge d_2\},$ define

where $\sigma_1\geq\sigma_2\geq\cdots\geq\sigma_{d_1\wedge d_2}\geq 0$ are the singular values of $A$. Clearly, $\Phi_k(A)$ is a symmetric gauge function and $\Phi_k(A) = \|A\|_{(k)}$. Furthermore, denote $\Psi_k$ the dual symmetric gauge function of $\Phi_k$, then for any $U\in\mathbb{O}_{d_1}, V\in\mathbb{O}_{d_2}$, we have $\Psi_k(U^TXV^T) = \Psi_k(X)$ and

This along with Lemma 2.1 shows that

where $\xi_1\geq\cdots\geq\xi_{d_1\wedge d_2}\geq 0$ are the singular values of $X$.

For any $U\in\mathbb{O}_{d, r}$, $P_U = UU^T$ is the projection matrix onto the column span of $U$. The next technical lemma is useful in the proof of Theorem 1.1.

Lemma 2.3. Let $\hat{A} = A+E\in \mathbb{R}^{d_1\times d_2}$, ${\rm rank}(A) = r$, and (1.2) holds. Then for any $k\in\{1, 2, \ldots, d_1\wedge d_2\}$,

Proof. Since ${\rm rank}(P_{\hat{U}_\bot}A)\leq{\rm rank}(A) = r$, and (2.3) of Lemma 2.2 are satisfied, we have

According to Lemma 2.2 and (2.2),

In addition, $\left\|\Big(P_{\hat{U}_\bot}\hat{A}\Big)_r\right\|_{(k)} = \left\|\Big(\hat{A}-\hat{A}_r\Big)_r\right\|_{(k)}$ due to $P_{\hat{U}}\hat{A} = \hat{A}_r$. On the other hand, based on Theorem 2 in ^[8] and the fact that the norm $\|(\cdot)_r\|_{(k)}$ is unitarily invariant, we have

Therefore,

For two matrices $B, C\in\mathbb{R}^{d_1\times d_2}$, it is known that

Thus, $\sigma_i(P_{{U}_\bot}E)\leq \sigma_1(P_{{U}_\bot})\sigma_i(E) = \sigma_i(E)$ and $\sigma_i(P_{{\hat{U}}_\bot}E)\leq \sigma_i(E)$. Hence, by (2.4),

Similarly, $\|A P_{\hat{V}_\bot}\|_{(k)}\leq2\|E_r\|_{(k)}.$ This completes the proof of Lemma 2.3.

2.2.   Proof of Theorem 1.1

Now, we are in the position to prove Theorem 1.1.

Proof. By (1.2), we know that $\hat{U}$ is composed of the first $r$ left singular vectors of $\hat{A}$. Thus, $\hat{A}_r = P_{\hat{U}}\hat{A}$. For any $k\in\{1, 2, \ldots, d_1\wedge d_2\},$

This with (2.5) and Lemma 2.3 derives

The proof of Theorem 1.1 is complete.

2.3.   Proof of Theorem 1.2

Proof. First, for any $k\leq r$, define $A_i, E_i\in\mathbb{R}^{d_1\times d_2}\; (i = 1, 2)$ with

then we have $A_1+E_1 = A_2+E_2 = \hat{A}$ and ${\rm rank}(A_1) = {\rm rank}(A_2) = r$. Where ${\rm rank}(A_1) = {\rm rank}(A_2) = r$ and $\left\|\Big(E_1\Big)_r\right\|_{(k)} = \left\|\Big(E_2\Big)_r\right\|_{(k)} = \frac{k}{k}t = t$. Therefore, $(A_1, E_1), (A_2, E_2)\in\mathcal{F}_r(t)$.

For any estimator $\tilde{A}$ of $A$, one derives

Next to show Theorem 1.2 is established for $k > r$. One takes

Then $A_1+E_1 = A_2+E_2 = \hat{A}$, ${\rm rank}(A_1) = {\rm rank}(A_2) = r$ and $\left\|\Big(E_1\Big)_r\right\|_{(k)} = \left\|\Big(E_2\Big)_r\right\|_{(k)} = t$. Therefore, $(A_1, E_1), (A_2, E_2)\in\mathcal{F}_r(t)$. We can use similar processes to prove (2.6). i.e.,

Theorem 1.2 is finished.

3.   Perturbation bounds of singular subspaces

As a byproduct of the perturbation theory, this paper derives $\sin\Theta$ perturbation bounds of the left and right subspaces $U, V$ under Ky Fan norm.

3.1.   Upper bounds

Theorem 3.1. Let $\hat{A} = A+E\in \mathbb{R}^{d_1\times d_2}$, ${\rm rank}(A) = r$. If the singular value decompositions(1.1) and (1.2) hold, then

for any $k\in\{1, 2, \ldots, d_1\wedge d_2\}$.

Proof. By Theorem 3.9 (II) in ^[9], one knows $\|BC^T\|_{(k)}\geq\|B\|_{(k)}\sigma_{d_1\wedge d_2}(C)$ for any two matrices $B, C\in\mathbb{R}^{d_1\times d_2}$. This with (1.6) shows

According to (1.1) and ${\rm rank}(A) = r$, one has $UU^TA = A$ and $\sigma_r(U^TA) = \sigma_r(A)$. Thus

thanks to Lemma 2.3. Similarly, one also can get $\|\sin\Theta(\hat{V}, V)\|_{(k)}\leq\frac{2\|E_r\|_{(k)}}{\sigma_r(A)}$. We have concluded the proof of Theorem 3.1.

3.2.   Lower bounds

Theorem 3.2. For $k\in\{1, 2, \ldots, d_1\wedge d_2\},$ define the following class

If $r\leq\frac{1}{2}(d_1\wedge d_2)$ and $\alpha(k\wedge r)\geq \beta$, then for any estimators $\tilde{U}$ and $\tilde{V}$ based on the observation matrix $A+E$, we have

Proof. We only need to show (3.2) since the statement (3.1) can be gotten by similar process. First, we introduce the following singular value decomposition,

then by Lemma 3 in ^[2] and $\alpha(k\wedge r)\geq \beta$, we know

Second, based on the above matrix, the following matrices are constructed.

Obviously, ${\rm rank}(A_1) = {\rm rank}(A_2) = r$ and

On the other hand, It is easy to check $\sigma_r(A_1) = \sigma_1(A_1)\geq \alpha, \left\|\Big(E_1\Big)_r\right\|_{(k)} = 0\leq\beta$ and $\sigma_r(A_2) = \alpha, \left\|\Big(E_1\Big)_r\right\|_{(k)} = \frac{k\wedge r}{k\wedge r}\beta\leq\beta.$ Hence, $(A_1, E_1), (A_2, E_2)\in\mathcal{F}_r(\alpha, \beta)$. Let $V_1, V_2$ are the leading $r$ singular vector of $A_1, A_2$ respectively, then

follow from the structure of $A_1, A_2$, Therefore, for any estimator $\tilde{V}$ of the leading $r$ right singular space, we have

The proof of Theorem 3.2 is finished.

Remark 3.1. In Theorem 3.2, the assumption $\alpha(k\wedge r)\geq \beta$ is necessary to obtain a consistent estimator. In fact, if $\alpha(k\wedge r) < \beta$, there is no stable algorithm to recover either $U$ or $V$ in the sense that there exists uniform constant $\frac{1}{2\sqrt{2}}$ such that

Proof. Let

then by Lemma 3 in ^[2] and $\alpha(k\wedge r) < \beta$, we know $|v_{21}|\geq \frac{1}{\sqrt{2}}.$ Therefore, based on the similar discussion of the proof of Theorem 3.2, Remark 3.1 is established.

Remark 3.2. By Theorem 3.2, we can know that the rates given in Theorem 3.1 are optimal, but the corresponding lower bounds for the singular subspaces are not given in Luo et al. ^[6].

4.   Numerical simulations

In this section, we provide some numerical studies to support our theoretical results. Throughout the simulation studies, we consider the nuclear norm $\|\cdot\|_*$ (the sum of all singular values) as the error metric. i.e., $k = d_1\wedge d_2$. Without loss of generality, we assume $d_1 = d_2: = d$. In each setting, we randomly generate the perturbation $E = uv^T+Z\in\mathbb{R}^{d\times d}$, where $u, v\in{\mathbb{R}^d}$ are randomly generated unit vectors and $Z$ has independent identically distributed $N(0, \sigma)$ entries. On the other hand, we generate low-rank matrix $A = U\Sigma_rV^T$ by a special structure. Here $U, V\in\mathbb{R}^{d\times r}$ are independently drawn from $\mathbb{O}_{d, r}$ uniformly at random; $\Sigma_r$ is a $r\times r$ diagonal matrix with singular values decaying polynomially as $(\Sigma_r)_{ii} = \frac{10}{i}, \; 1\leq i\leq r$. Each simulation setting is repeated for 100 times and the average values are reported. The Figure 1 is the result of numerical studies.

We set $d\in\{100,200\}, \; r\in\{3, 6, 9, 12, 15\}, \; \sigma = 0.004$. The results of the upper bounds in Theorem 1.1, (1.3) and the true value of $\|\hat{A}_r-A\|_*$ are given in Figure 1. It shows that the upper bound in Theorem 1.1 is tighter than the upper bound in (1.3) in all setting. Furthermore, the upper bound of Theorem 1.1 remains steady while the upper bound of (1.3) significantly increases when $d$ increases form 100 to 200.

5.   Conclusions

In this paper, we give a sharp upper bound for rank-$r$ matrix $A$ under Ky Fan norm, and show that it is optimal by establishing the corresponding lower bound. As a byproduct, we provide the perturbation bounds for the singular subspaces under Ky Fan norm $\sin\Theta$ distance. Furthermore, we give the corresponding lower bound to show its optimality. Finally, we provide numerical studies to support our theoretical results.

As a unitarily invariant norm, Ky Fan norm which is different from Schatten-$q$ norm is also an important matrix norm. So it makes sense to study the perturbation bound for the low-rank matrix. It is worth mentioning that the approach of proving Lemma 2.3 can be generalized any unitarily invariant norm. Therefore, it can be used to study other perturbation theory in future.

Acknowledgments

The authors would like to express their gratitude to the editor and anonymous referees for their constructive and valuable suggestions which improved the paper. This work is supported by the National Natural Science Foundation of China (No. 11771030 and 12171016).

Conflict of interest

The authors declare that they have no conflicts of interest.