A useful variant of the Davis--Kahan theorem for statisticians

Introduction

Many statistical procedures rely on the eigendecomposition of a matrix. Examples include principal components analysis and its cousin sparse principal components analysis (Zou et al., 2006), factor analysis, high-dimensional covariance matrix estimation (Fan et al., 2013) and spectral clustering for community detection with network data (Donath and Hoffman, 1973). In these and most other related statistical applications, the matrix involved is real and symmetric, e.g. a covariance or correlation matrix, or a graph Laplacian or adjacency matrix in the case of spectral clustering.

Since we may reverse the sign of $\hat{v}_{j}$ if necessary, there is a choice of orientation of $\hat{v}_{j}$ for which $\hat{v}_{j}^{T}v_{j}\geq 0$. For this choice, we can also deduce that $\|\hat{v}_{j}-v_{j}\|\leq\sqrt{2}\sin\Theta(\hat{v}_{j},v_{j})$.

This theorem is then used to show that $\hat{v}_{j}$ is close to $v_{j}$ as follows: first, we argue that $\hat{\Sigma}$ is close to $\Sigma$. This is often straightforward; for instance, when $\Sigma$ is a population covariance matrix, it may be that $\hat{\Sigma}$ is just an empirical average of independent and identically distributed random matrices. Then we argue, e.g. using Weyl’s inequality, that with high probability, $|\hat{\lambda}_{j-1}-\lambda_{j}|\geq(\lambda_{j-1}-\lambda_{j})/2$ and $|\hat{\lambda}_{j+1}-\lambda_{j}|\geq(\lambda_{j}-\lambda_{j+1})/2$, so on these events $\|\hat{v}_{j}-v_{j}\|$ is small provided we are willing to assume an eigenvalue separation, or eigen-gap, condition on the population eigenvalues.

The main contribution of this paper is to give a variant of the Davis–Kahan theorem in Theorem 2 in Section 2 below, where the only eigen-gap condition is on the population eigenvalues, by contrast with the definition of $\delta$ in Theorem 1 above. Similarly, only population eigenvalues appear in the denominator of the bounds. This means there is no need for the statistician to worry about the event where $|\hat{\lambda}_{j+1}-\lambda_{j+1}|$ or $|\hat{\lambda}_{j-1}-\lambda_{j-1}|$ is small. In Section 3, we give a selection of several examples where the Davis–Kahan theorem has been used in the statistical literature, and where our results could be applied directly to allow those authors to assume more natural conditions, to simplify proofs, and in some cases, to improve bounds.

Singular value decomposition, which may be regarded as a generalisation of eigendecomposition, but which exists even when a matrix is not square, also plays an important role in many modern algorithms in Statistics and machine learning. Examples include matrix completion (Candès and Recht, 2009), robust principal components analysis (Candès et al., 2009) and motion analysis (Kukush et al., 2002), among many others. Wedin (1972) provided the analogue of the Davis–Kahan theorem for such general real matrices, working with singular vectors rather than eigenvectors, but with conditions and bounds that mix sample and population singular values. In Section 4, we extend the results of Section 2 to such settings; again our results depend only on a condition on the population singular values. Proofs are deferred to the Appendix.

Main results

Many if not most applications of this result will only need $s=r$, i.e. $d=1$. In that case, the statement simplifies a little; for ease of reference, we state it as a corollary:

Applications of the Davis–Kahan theorem in statistical contexts

In this section, we give several examples of ways in which the Davis–Kahan $\sin\theta$ theorem has been applied in the statistical literature. Our selection is by no means exhaustive – indeed there are many others of a similar flavour – but it does illustrate a range of applications. In fact, we also found some instances in the literature where a version of the Davis–Kahan theorem with a population eigen-gap condition was used without justification. In all of the examples below, our results can be applied directly to impose more natural conditions, to simplify the proofs and, in some cases, to improve the bounds.

Fan et al. (2013) study large covariance matrix estimation problems where the population covariance matrix can be represented as the sum of a low rank matrix and a sparse matrix. Their Proposition 2 uses the operator norm version of Theorem 1 with $d=1$. They then use a further bound from Weyl’s inequality and a population eigen-gap condition as outlined in the introduction to control the norm of the difference between the leading sample and population eigenvectors. Mitra and Zhang (2014) apply the theorem in a very similar way, but for general $d$ and for large correlation matrices as opposed to covariance matrices. Again in the same spirit, Fan and Han (2013) apply the result with $d=1$ to the problem of estimating the false discovery proportion in large-scale multiple testing with highly correlated test statistics. Other similar applications include El Karoui (2008), who derives consistency of sparse covariance matrix estimators, Cai et al. (2013), who study sparse principal component estimation, and Wang and Nyquist (1991), who consider how eigenstructure is altered by deleting an observation.

von Luxburg (2007), Rohe et al. (2011), Amini et al. (2013) and Bhattacharyya and Bickel (2014) use the Davis–Kahan $\sin\theta$ theorem as a way of providing theoretical justification for spectral clustering in community detection with network data. Here, the matrices of interest include graph Laplacians and adjacency matrices, both of which may or may not be normalised. In these works, the statement of the Davis–Kahan theorem given is a slight variant of Theorem 1, and it may appear from, e.g. Proposition B.1 of Rohe et al. (2011), that only a population eigen-gap condition is assumed. However, careful inspection reveals that $\Sigma$ and $\hat{\Sigma}$ must have the same number of eigenvalues in the interval of interest, so that their condition is essentially the same as that in Theorem 1.

Extension to general real matrices

We now describe how the results of Section 2 can be extended to situations where the matrices under study may not be symmetric and may not even be square, and where interest is in controlling the principal angles between corresponding singular vectors.

As mentioned in the introduction, Theorem 4 can be viewed as a variant of the ‘generalized $\sin\theta$’ theorem of Wedin (1972). Again, the main difference is that our condition only requires a gap between the relevant population singular values.

Similar to the situation for symmetric matrices, there are many places in the statistical literature where Wedin’s result has been used, but where we argue that Theorem 4 above would be a more natural result to which to appeal. Examples include the papers of Van Huffel and Vandewalle (1989) on the accuracy of least squares techniques, Anandkumar et al. (2014) on tensor decompositions for learning latent variable models, Shabalin and Nobel (2013) on recovering a low rank matrix from a noisy version and Sun and Zhang (2012) on matrix completion.

Acknowledgements

The first and third authors are supported by the third author’s Engineering and Physical Sciences Research Council Early Career Fellowship EP/J017213/1. The second author is supported by a Benefactors’ scholarship from St John’s College, Cambridge.

Appendix

We first state an elementary lemma that will be useful in several places.

where we have used Lemma 5 in the second inequality and Weyl’s inequality (e.g. Stewart and Sun, 1990, Corollary 4.9) for the final bound. Alternatively, we can argue that

where the second inequality follows from two applications of Lemma 5, and the final inequality follows from the Wielandt–Hoffman theorem (e.g. Wilkinson, 1965, pp. 104–108).

We deduce from (5), (5), (5) and (5) that

The result now follows from our first conclusion. ∎

Now, by the submultiplicity of the operator norm,

References