Less is More: Nyström Computational Regularization

Introduction

Kernel methods provide an elegant and effective framework to develop nonparametric statistical approaches to learning [schlkopf2002learning]. However, memory requirements make these methods unfeasible when dealing with large datasets. Indeed, this observation has motivated a variety of computational strategies to develop large scale kernel methods [conf/icml/SmolaS00, conf/nips/WilliamsS00, conf/nips/RahimiR07, conf/icml/YangSAM14, conf/icml/LeSS13, conf/icml/SiHD14, conf/colt/ZhangDW13]. In this paper we study subsampling methods, that we broadly refer to as Nyström approaches. These methods replace the empirical kernel matrix, needed by standard kernel methods, with a smaller matrix obtained by (column) subsampling [conf/icml/SmolaS00, conf/nips/WilliamsS00]. Such procedures are shown to often dramatically reduce memory/time requirements while preserving good practical performances [conf/nips/KumarMT09, conf/icml/LiKL10, Zhang:2008:INL:1390156.1390311, conf/nips/DaiXHLRBS14]. The goal of our study is two-fold. First, and foremost, we aim at providing a theoretical characterization of the generalization properties of such learning schemes in a statistical learning setting. Second, we wish to understand the role played by the subsampling level both from a statistical and a computational point of view. As discussed in the following, this latter question leads to a natural variant of Kernel Regularized Least Squares (KRLS), where the subsampling level controls both regularization and computations.

From a theoretical perspective, the effect of Nyström approaches has been primarily characterized considering the discrepancy between a given empirical kernel matrix and its subsampled version [Drineas:2005:NMA:1046920.1194916, gittens2013revisiting, Wang:2013:ICM:2567709.2567748, journals/jmlr/DrineasMMW12, conf/innovations/CohenLMMPS15, conf/aistats/WangZ14, Kumar:2012:SMN:2503308.2343678]. While interesting in their own right, these latter results do not directly yield information on the generalization properties of the obtained algorithm. Results in this direction, albeit suboptimal, were first derived in [journals/jmlr/CortesMT10] (see also [6547995, conf/nips/YangLMJZ12]), and more recently in [conf/colt/Bach13, alaoui2014fast]. In these latter papers, sharp error analyses in expectation are derived in a fixed design regression setting for a form of Kernel Regularized Least Squares. In particular, in [conf/colt/Bach13] a basic uniform sampling approach is studied, while in [alaoui2014fast] a subsampling scheme based on the notion of leverage score is considered. The main technical contribution of our study is an extension of these latter results to the statistical learning setting, where the design is random and high probability estimates are considered. The more general setting makes the analysis considerably more complex. Our main result gives optimal finite sample bounds for both uniform and leverage score based subsampling strategies. These methods are shown to achieve the same (optimal) learning error as kernel regularized least squares, recovered as a special case, while allowing substantial computational gains. Our analysis highlights the interplay between the regularization and subsampling parameters, suggesting that the latter can be used to control simultaneously regularization and computations. This strategy implements a form of computational regularization in the sense that the computational resources are tailored to the generalization properties in the data. This idea is developed considering an incremental strategy to efficiently compute learning solutions for different subsampling levels. The procedure thus obtained, which is a simple variant of classical Nyström Kernel Regularized Least Squares with uniform sampling, allows for efficient model selection and achieves state of the art results on a variety of benchmark large scale datasets. The rest of the paper is organized as follows. In Section 2, we introduce the setting and algorithms we consider. In Section 3, we present our main theoretical contributions. In Section 4, we discuss computational aspects and experimental results.

Supervised learning with KRLS and \Nystrom approaches

provided $\rho$ is known only through a training set of $(x_{i},y_{i})_{i=1}^{n}$ sampled identically and independently according to $\rho$. A basic example of the above setting is random design regression with the squared loss, in which case

The above approach is referred to as Kernel Regularized Least Squares (KRLS) or Kernel Ridge Regression (KRR). It is easy to see that a solution $\hat{f}_{\lambda}$ to problem (3) exists, it is unique and the representer theorem [schlkopf2002learning] shows that it can be written as

where $x_{1},\dots,x_{n}$ are the training set points, $y=(y_{1},\dots,y_{n})$ and ${K_{n}}$ is the empirical kernel matrix. Note that this result implies that we can restrict the minimization in (3) to the space,

Storing the kernel matrix ${K_{n}}$, and solving the linear system in (4), can become computationally unfeasible as $n$ increases. In the following, we consider strategies to find more efficient solutions, based on the idea of replacing $\mathcal{H}_{n}$ with

for any $t>0$, where $(K_{n})_{ij}=K(x_{i},x_{j})$. In practice, leverage scores are onerous to compute and approximations $(\hat{l}_{i}(t))_{i=1}^{n}$ can be considered [journals/jmlr/DrineasMMW12, alaoui2014fast, conf/innovations/CohenLMMPS15] . In particular, in the following we are interested in suitable approximations defined as follows:

Let $(l_{i}(t))_{i=1}^{n}$ be the leverage scores associated to the training set for a given $t$. Let $\delta>0$, $t_{0}>0$ and $T\geq 1$. We say that $(\widehat{l}_{i}(t))_{i=1}^{n}$ are $T$-approximate leverage scores with confidence $\delta$, when with probability at least $1-\delta$,

Theoretical analysis

In this section, we state and discuss our main results. We need several assumptions. The first basic assumption is that problem (1) admits at least a solution.

There exists an $f_{\mathcal{H}}\in\mathcal{H}$ such that

Note that, while the minimizer might not be unique, our results apply to the case in which $f_{\mathcal{H}}$ is the unique minimizer with minimal norm. Also, note that the above condition is weaker than assuming the regression function in (2) to belong to $\mathcal{H}$. Finally, we note that the study of the paper can be adapted to the case in which minimizers do not exist, but the analysis is considerably more involved and left to a longer version of the paper. The second assumption is a basic condition on the probability distribution.

The above assumption is needed to control random quantities and is related to a noise assumption in the regression model (2). It is clearly weaker than the often considered bounded output assumption [steinwart2008support], and trivially verified in classification. The last two assumptions describe the capacity (roughly speaking the “size”) of the hypothesis space induced by $K$ with respect to $\rho$ and the regularity of $f_{\mathcal{H}}$ with respect to $K$ and $\rho$. To discuss them, we first need the following definition.

Moreover, for $\lambda>0$, we define the random variable ${\cal N}_{x}(\lambda)=\left\langle{K_{x}},{(C+\lambda I)^{-1}K_{x}}\right\rangle_{\mathcal{H}}$ with $x\in{X}$ distributed according to ${\rho_{{X}}}$ and let

We add several comments. Note that $C$ corresponds to the second moment operator, but we refer to it as the covariance operator with an abuse of terminology. Moreover, note that ${\cal N}(\lambda)=\operatorname{Tr}(C(C+\lambda I)^{-1})$ (see [caponnetto2007optimal]). This latter quantity, called effective dimension or degrees of freedom, can be seen as a measure of the capacity of the hypothesis space. The quantity ${\cal N}_{\infty}(\lambda)$ can be seen to provide a uniform bound on the leverage scores in Eq. (6). Clearly, ${\cal N}(\lambda)\leq{\cal N}_{\infty}(\lambda)$ for all $\lambda>0$.

The kernel $K$ is measurable, $C$ is bounded. Moreover, for all $\lambda>0$ and a $Q>0$,

Measurability of $K$ and boundedness of $C$ are minimal conditions to ensure that the covariance operator is a well defined linear, continuous, self-adjoint, positive operator [steinwart2008support]. Condition (7) is satisfied if the kernel is bounded $\sup_{x\in{X}}K(x,x)=\kappa^{2}<\infty$, indeed in this case ${\cal N}_{\infty}(\lambda)\leq\kappa^{2}/\lambda$ for all $\lambda>0$. Conversely, it can be seen that condition (7) together with boundedness of $C$ imply that the kernel is bounded, indeed If ${\cal N}_{\infty}(\lambda)$ is finite, then ${\cal N}_{\infty}(\lVert{C}\rVert)=\textrm{sup}_{x\in X}\lVert{(C+\lVert{C}\rVert I)^{-1}K_{x}}\rVert^{2}\geq 1/2\lVert{C}\rVert^{-1}\textrm{sup}_{x\in X}\lVert{K_{x}}\rVert^{2}$, therefore $K(x,x)\leq 2\lVert{C}\rVert{\cal N}_{\infty}(\lVert{C}\rVert)$.

Boundedness of the kernel implies in particular that the operator $C$ is trace class and allows to use tools from spectral theory. Condition (8) quantifies the capacity assumption and is related to covering/entropy number conditions (see [steinwart2008support] for further details). In particular, it is known that condition (8) is ensured if the eigenvalues $(\sigma_{i})_{i}$ of $C$ satisfy a polynomial decaying condition $\sigma_{i}\sim i^{-\frac{1}{\gamma}}$. Note that, since the operator $C$ is trace class, Condition (8) always holds for $\gamma=1$. Here, for space constraints and in the interest of clarity we restrict to such a polynomial condition, but the analysis directly applies to other conditions including exponential decay or a finite rank conditions [caponnetto2007optimal]. Finally, we have the following regularity assumption.

There exists $s\geq 0$, $1\leq R<\infty$, such that $\lVert{C^{-s}f_{\mathcal{H}}}\rVert_{\mathcal{H}}<R$.

The above condition is fairly standard, and can be equivalently formulated in terms of classical concepts in approximation theory such as interpolation spaces [steinwart2008support]. Intuitively, it quantifies the degree to which $f_{\mathcal{H}}$ can be well approximated by functions in the RKHS $\mathcal{H}$ and allows to control the bias/approximation error of a learning solution. For $s=0$, it is always satisfied. For larger $s$, we are assuming $f_{\mathcal{H}}$ to belong to subspaces of $\mathcal{H}$ that are the images of the fractional compact operators $C^{s}$. Such spaces contain functions which, expanded on a basis of eigenfunctions of $C$, have larger coefficients in correspondence to large eigenvalues. Such an assumption is natural in view of using techniques such as (4), which can be seen as a form of spectral filtering, that estimate stable solutions by discarding the contribution of small eigenvalues [journals/neco/GerfoROVV08]. In the next section, we are going to quantify the quality of empirical solutions of Problem (1) obtained by schemes of the form (5), in terms of the quantities in Assumptions 2, 3, 4.

In this section, we state and discuss our main results, starting with optimal finite sample error bounds for regularized least squares based on plain and approximate leverage score based \Nystrom subsampling.

Under Assumptions 1, 2, 3, and 4, let $\delta>0$, $v=\min(s,1/2)$, $p=1+1/(2v+\gamma)$ and assume

Then, the following inequality holds with probability at least $1-\delta$,

with $\hat{f}_{\lambda,m}$ as in (5), $\lambda=\lVert{C}\rVert n^{-\frac{1}{2v+\gamma+1}}$ and

for ALS \Nystrom and $T$-approximate leverage scores with subsampling probabilities $P_{\lambda}$, $t_{0}\geq\frac{19\kappa^{2}}{n}\log\frac{12n}{\delta}$ and

We add several comments. First, the above results can be shown to be optimal in a minimax sense. Indeed, minimax lower bounds proved in [caponnetto2007optimal, SteinwartHS09] show that the learning rate in (9) is optimal under the considered assumptions (see Thm. 2, 3 of [caponnetto2007optimal], for a discussion on minimax lower bounds see Sec. 2 of [caponnetto2007optimal]). Second, the obtained bounds can be compared to those obtained for other regularized learning techniques. Techniques known to achieve optimal error rates include Tikhonov regularization [caponnetto2007optimal, SteinwartHS09, mendelson2010regularization], iterative regularization by early stopping [bauer, CapYao06], spectral cut-off regularization (a.k.a. principal component regression or truncated SVD) [bauer, CapYao06], as well as regularized stochastic gradient methods [yiming]. All these techniques are essentially equivalent from a statistical point of view and differ only in the required computations. For example, iterative methods allow for a computation of solutions corresponding to different regularization levels which is more efficient than Tikhonov or SVD based approaches. The key observation is that all these methods have the same $O(n^{2})$ memory requirement. In this view, our results show that randomized subsampling methods can break such a memory barrier, and consequently achieve much better time complexity, while preserving optimal learning guarantees. Finally, we can compare our results with previous analysis of randomized kernel methods. As already mentioned, results close to those in Theorem 1 are given in [conf/colt/Bach13, alaoui2014fast] in a fixed design setting. Our results extend and generalize the conclusions of these papers to a general statistical learning setting. Relevant results are given in [conf/colt/ZhangDW13] for a different approach, based on averaging KRLS solutions obtained splitting the data in $m$ groups (divide and conquer RLS). The analysis in [conf/colt/ZhangDW13] is only in expectation, but considers random design and shows that the proposed method is indeed optimal provided the number of splits is chosen depending on the effective dimension ${\cal N}(\lambda)$. This is the only other work we are aware of establishing optimal learning rates for randomized kernel approaches in a statistical learning setting. In comparison with \Nystrom computational regularization the main disadvantage of the divide and conquer approach is computational and in the model selection phase where solutions corresponding to different regularization parameters and number of splits usually need to be computed. The proof of Theorem 1 is fairly technical and lengthy. It incorporates ideas from [caponnetto2007optimal] and techniques developed to study spectral filtering regularization [bauer, rudi2013sample]. In the next section, we briefly sketch some main ideas and discuss how they suggest an interesting perspective on regularization techniques including subsampling.

2 Proof sketch and a computational regularization perspective

A key step in the proof of Theorem 1 is an error decomposition, and corresponding bound, for any fixed $\lambda$ and $m$. Indeed, it is proved in Theorem 2 and Proposition 2 that, for $\delta>0$, with probability at least $1-\delta$,

The first and last term in the right hand side of the above inequality can be seen as forms of sample and approximation errors [steinwart2008support] and are studied in Lemma 4 and Theorem 2. The mid term can be seen as a computational error and depends on the considered subsampling scheme. Indeed, it is shown in Proposition 2 that ${\cal C}(m)$ can be taken as,

for the approximate leverage scores approach. The bounds in Theorem 1 follow by: 1) minimizing in $\lambda$ the sum of the first and third term 2) choosing $m$ so that the computational error is of the same order of the other terms. Computational resources and regularization are then tailored to the generalization properties of the data at hand. We add a few comments. First, note that the error bound in (10) holds for a large class of subsampling schemes, as discussed in Section C.1 in the appendix. Then specific error bounds can be derived developing computational error estimates. Second, the error bounds in Theorem 2 and Proposition 2, and hence in Theorem 1, easily generalize to a larger class of regularization schemes beyond Tikhonov approaches, namely spectral filtering [bauer]. For space constraints, these extensions are deferred to a longer version of the paper. Third, we note that, in practice, optimal data driven parameter choices, e.g. based on hold-out estimates [CapYao06], can be used to adaptively achieve optimal learning bounds. Finally, we observe that a different perspective is derived starting from inequality (10), and noting that the role played by $m$ and $\lambda$ can also be exchanged. Letting $m$ play the role of a regularization parameter, $\lambda$ can be set as a function of $m$ and $m$ tuned adaptively. For example, in the case of a plain \Nystrom approach, if we set

then the obtained learning solution achieves the error bound in Eq. (9). As above, the subsampling level can also be chosen by cross-validation. Interestingly, in this case by tuning $m$ we naturally control computational resources and regularization. An advantage of this latter parameterization is that, as described in the following, the solution corresponding to different subsampling levels is easy to update using Cholesky rank-one update formulas [Golub1996]. As discussed in the next section, in practice, a joint tuning over $m$ and $\lambda$ can be done starting from small $m$ and appears to be advantageous both for error and computational performances.

Incremental updates and experimental analysis

In this section, we first describe an incremental strategy to efficiently explore different subsampling levels and then perform extensive empirical tests aimed in particular at: 1) investigating the statistical and computational benefits of considering varying subsampling levels, and 2) compare the performance of the algorithm with respect to state of the art solutions on several large scale benchmark datasets. Throughout this section, we only consider a plain \Nystrom approach, deferring to future work the analysis of leverage scores based sampling techniques. Interestingly, we will see that such a basic approach can often provide state of the art performances.

2 Experimental analysis

We empirically study the properties of Algorithm 1, considering a Gaussian kernel of width $\sigma$. The selected datasets are already divided in a training and a test partIn the following we denote by $n$ the total number of points and by $d$ the number of dimensions.. We randomly split the training part in a training set and a validation set ($80\%$ and $20\%$ of the $n$ training points, respectively) for parameter tuning via cross-validation. The $m$ subsampled points for \Nystrom approximation are selected uniformly at random from the training set. We report the performance of the selected model on the fixed test set, repeating the process for several trials. Interplay between $\lambda$ and $m$. We begin with a set of results showing that incrementally exploring different subsampling levels can yield very good performance while substantially reducing the computational requirements. We consider the pumadyn32nh ($n=8192$, $d=32$), the breast cancer ($n=569$, $d=30$), and the cpuSmall ($n=8192$, $d=12$) datasetswww.cs.toronto.edu/~delve and archive.ics.uci.edu/ml/datasets. In Figure 1, we report the validation errors associated to a $20\times 20$ grid of values for $\lambda$ and $m$. The $\lambda$ values are logarithmically spaced, while the $m$ values are linearly spaced. The ranges and kernel bandwidths, chosen according to preliminary tests on the data, are $\sigma=2.66$, $\lambda\in\left[10^{-7},1\right]$, $m\in\left[10,1000\right]$ for pumadyn32nh, $\sigma=0.9$, $\lambda\in\left[10^{-12},10^{-3}\right]$, $m\in\left[5,300\right]$ for breast cancer, and $\sigma=0.1$, $\lambda\in\left[10^{-15},10^{-12}\right]$, $m\in\left[100,5000\right]$ for cpuSmall. The main observation that can be derived from this first series of tests is that a small $m$ is sufficient to obtain the same results achieved with the largest $m$. For example, for pumadyn32nh it is sufficient to choose $m=62$ and $\lambda=10^{-7}$ to obtain an average test RMSE of $0.33$ over 10 trials, which is the same as the one obtained using $m=1000$ and $\lambda=10^{-3}$, with a 3-fold speedup of the joint training and validation phase. Also, it is interesting to observe that for given values of $\lambda$, large values of $m$ can decrease the performance. This observation is consistent with the results in Section 3.1, showing that $m$ can play the role of a regularization parameter. Similar results are obtained for breast cancer, where for $\lambda=4.28\times 10^{-6}$ and $m=300$ we obtain a $1.24\%$ average classification error on the test set over 20 trials, while for $\lambda=10^{-12}$ and $m=67$ we obtain $1.86\%$. For cpuSmall, with $m=5000$ and $\lambda=10^{-12}$ the average test RMSE over 5 trials is $12.2$, while for $m=2679$ and $\lambda=10^{-15}$ it is only slightly higher, $13.3$, but computing its associated solution requires less than half of the time and approximately half of the memory.

Regularization path computation. If the subsampling level $m$ is used as a regularization parameter, the computation of a regularization path corresponding to different subsampling levels becomes crucial during the model selection phase. A naive approach, that consists in recomputing the solutions of Eq. 5 for each subsampling level, would require $O(m^{2}nT+m^{3}LT)$ computational time, where $T$ is the number of solutions with different subsampling levels to be evaluated and $L$ is the number of Tikhonov regularization parameters. On the other hand, by using the incremental \Nystrom algorithm the model selection time complexity is $O(m^{2}n+m^{3}L)$ for the whole regularization path. We experimentally verify this speedup on cpuSmall with 10 repetitions, setting $m\in\left[1,5000\right]$ and $T=50$. The model selection times, measured on a server with 12 $\times$ 2.10GHz Intel® Xeon® E5-2620 v2 CPUs and 132 GB of RAM, are reported in Figure 2. The result clearly confirms the beneficial effects of incremental \Nystrom model selection on the computational time. Predictive performance comparison. Finally, we consider the performance of the algorithm on several large scale benchmark datasets considered in [conf/icml/LeSS13], see Table 1. $\sigma$ has been chosen on the basis of preliminary data analysis. $m$ and $\lambda$ have been chosen by cross-validation, starting from small subsampling values up to $m_{max}=2048$, and considering $\lambda\in\left[10^{-12},1\right]$. After model selection, we retrain the best model on the entire training set and compute the RMSE on the test set. We consider 10 trials, reporting the performance mean and standard deviation. The results in Table 1 compare \Nystrom computational regularization with the following methods (as in [conf/icml/LeSS13]):

Kernel Regularized Least Squares (KRLS): Not compatible with large datasets.

Random Fourier features (RF): As in [conf/nips/RahimiR07], with a number of random features $D=2048$.

Fastfood RBF, FFT and Matern kernel: As in [conf/icml/LeSS13], with $D=2048$ random features.

Batch \Nystrom: \Nystrom method [conf/nips/WilliamsS00] with uniform sampling and $m=2048$.

The above results show that the proposed incremental \Nystrom approach behaves really well, matching state of the art predictive performances.

The work described in this paper is supported by the Center for Brains, Minds and Machines (CBMM), funded by NSF STC award CCF-1231216; and by FIRB project RBFR12M3AC, funded by the Italian Ministry of Education, University and Research.

References

Appendix A The incremental algorithm

Appendix B Preliminary definitions

Let $S_{n}=\frac{1}{\sqrt{n}}Z_{m}$ and $S_{n}^{*}=\frac{1}{\sqrt{n}}Z_{m}^{*}$ the operators obtained taking $m=n$ and $z_{i}=K_{x_{i}}$, $\forall i=1,\dots,n$ in the above definitions. Moreover, for all $f,g\in\mathcal{H}$ let

Appendix C Representer theorem for \Nystrom computational regularization and extensions

In this section we consider explicit representations of the estimator obtained via \Nystrom computational regularization and extensions. Indeed, we consider a general subspace $\mathcal{H}_{m}$ of $\mathcal{H}$, and the following problem

In the following lemmas, we show three different characterizations of $f_{\lambda,m}$.

Let $f_{\lambda,m}$ be the solution of the problem in Eq. (11). Then it is characterized by the following equation

with $P_{m}$ the projection operator with range $\mathcal{H}_{m}$ and $\widehat{y}_{n}=\frac{1}{\sqrt{n}}y$.

The proof proceeds in three steps. First, note that, by rewriting Problem (11) with the notation introduced in the previous section, we obtain,

This problem is strictly convex and coercive, therefore admits a unique solution. Second, we show that its solution coincide to the one of the following problem,

Note that the above problem is again strictly convex and coercive. To show that $\hat{f}_{\lambda,m}=\hat{f}^{*}$, let $\hat{f}^{*}=a+b$ with $a\in\mathcal{H}_{m}$ and $b\in\mathcal{H}_{m}^{\bot}$. A necessary condition for $\hat{f}^{*}$ to be optimal, is that $b=0$, indeed, considering that $P_{m}b=0$, we have

This means that $\hat{f}^{*}\in\mathcal{H}_{m}$, but on $\mathcal{H}_{m}$ the functionals defining Problem (13) and Problem (14) are identical because $P_{m}f=f$ for any $f\in\mathcal{H}_{m}$ and so $\hat{f}_{\lambda,m}=\hat{f}^{*}$. Therefore, by computing the derivative of the functional of Problem (14), we see that $\hat{f}_{\lambda,m}$ is given by Eq. (12). ∎

Using the above results, we can give an equivalent representations of the function $\hat{f}_{\lambda,m}$. Towards this end, let $Z_{m}$ be a linear operator as in Sect. B such that the range of $Z_{m}^{*}$ is exactly $\mathcal{H}_{m}$. Morever, let

Given the above definitions , $\hat{f}_{\lambda,m}$ can be written as

By Lemma 1, we know that $\hat{f}_{\lambda,m}$ is written as in Eq. (12). Now, note that $\hat{f}_{\lambda,m}=P_{m}\hat{f}_{\lambda,m}$ and Eq. (12) imply $(P_{m}{{C}}_{m}P_{m}+\lambda I)P_{m}\hat{f}_{\lambda,m}=P_{m}S_{n}^{*}\widehat{y}_{n}$, that is equivalent to

by substituting $P_{m}$ with $VV^{*}$. Thus by premultiplying the previous equation by $V^{*}$ and dividing by $V^{*}{{C}}_{m}V+\lambda I$, we have

Finally, the following result provide a characterization of the solution useful for computations.

Given the above definitions, we have that $\hat{f}_{\lambda,m}$ can be written as

According to the definitions of $B_{nm}$ and $G_{mm}$ we have that

Moreover, according to the definition of $Z_{m}$ we have

where ${{C}}_{n\lambda}=C_{n}+\lambda I$. Let $F=U\Sigma$, $G=V^{*}{{C}}_{n}V+\lambda I$, $H=\Sigma U^{\top}$, and note that $F$, $GH$, $G$ and $H$ are full-rank matrices, then we can perform the full-rank factorization of the pseudo-inverse (see Eq.24, Thm. 5, Chap. 1 of [ben2003generalized]) obtaining

Finally, simplyfing $U$ and $\Sigma$, we have

Inspection of the proof shows that our analysis extends beyond the class of subsampling schemes in Theorem 1. Indeed, the error decomposition Theorem 2 directly applies to a large family of approximation schemes. Several further examples are described next.

Without loss of generality, $Z_{m}^{*}$ is expressible as $Z_{m}^{*}=(z_{1},\dots,z_{m})^{\top}$ with $z_{1},\dots,z_{m}\in\mathcal{H}$, therefore, according to Section B and to Lemma 3, the solution of KRLS approximated with the generalized \Nystrom scheme is

The following are some examples of Generalized \Nystrom approximations.

Appendix D Probabilistic inequalities

The first result is essentially taken from [caponnetto2007optimal].

Under Assumptions 1, 2 and 3, for any $\delta>0$, the following holds with probability $1-\delta$

The proof is given in [caponnetto2007optimal] for bounded kernels and the slightly stronger condition $\int(e^{\frac{|y-f_{\mathcal{H}}(x)|}{M}}-\frac{|y-f_{\mathcal{H}}(x)|}{M}-1)d\rho(y|x)\leq\sigma^{2}/M^{2}$ in place of Assumption 2. More precisely, note that

where $\zeta_{1},\dots,\zeta_{n}$ are i.i.d. random variables, defined as $\zeta_{i}=(C+\lambda I)^{-1/2}K_{x_{i}}(y_{i}-f_{\mathcal{H}}(x_{i}))$. For any $1\leq i\leq n$,

almost everywhere by Assumption 1 (see Step 3.2 of Thm. 4 in [caponnetto2007optimal]). In the same way we have

where $\sup_{x\in{X}}\lVert{(C+\lambda I)^{-1/2}K_{x}}\rVert=\sqrt{{\cal N}_{\infty}(\lambda)}$ and $\int_{X}\lVert{(C+\lambda I)^{-1/2}K_{x_{i}}}\rVert^{2}={\cal N}(\lambda)$ by Assumption 3, while the bound on the moments of $y-f(x)$ is given in Assumption 2. Finally, to concentrate the sum of random vectors, we apply Prop. 11. ∎

The next result is taken from [rudi2013sample].

Under Assumption 3, for any $\delta\geq 0$ and $\frac{9\kappa^{2}}{n}\log\frac{n}{\delta}\leq\lambda\leq\lVert{C}\rVert$, the following inequality holds with probability at least $1-\delta$,

Lemma 7 of [rudi2013sample] gives an the extended version of the above result. Our bound on $\lambda$ is scaled by $\kappa^{2}$ because in [rudi2013sample] it is assumed $\kappa\leq 1$. ∎

Under Assumption 3, let $J$ be a partition of $\{1,\dots,n\}$ chosen uniformly at random from the partitions of cardinality $m$. Let $\lambda>0$, for any $\delta>0$, such that $m\geq 67\log\frac{4\kappa^{2}}{\lambda\delta}\,\vee\,5{\cal N}_{\infty}(\lambda)\log\frac{4\kappa^{2}}{\lambda\delta}$, the following holds with probability $1-\delta$

where $P_{m}$ is the projection operator on the subspace $\mathcal{H}_{m}=\operatorname{span}\{K_{x_{j}}~{}|~{}j\in J\}$.

Define the linear operator ${{C}}_{m}:\mathcal{H}\to\mathcal{H}$, as ${{C}}_{m}=\frac{1}{m}\sum_{j\in J}K_{x_{j}}\otimes K_{x_{j}}$. Now note that the range of ${{C}}_{m}$ is exactly $\mathcal{H}_{m}$. Therefore, by applying Prop. 3 and 7, we have that

with $\beta(\lambda)=\lambda_{\max}\left({C}_{\lambda}^{-1/2}({C}-{{C}}_{m}){C}_{\lambda}^{-1/2}\right)$. To upperbound $\frac{\lambda}{1-\beta(\lambda)}$ we need an upperbound for $\beta(\lambda)$. Considering that, given the partition $J$, the random variables $\zeta_{j}=K_{x_{j}}\otimes K_{x_{j}}$ are i.i.d., then we can apply Prop. 8, to obtain

where $w=\log\frac{4\operatorname{Tr}(C)}{\lambda\delta}$ with probability $1-\delta$. Thus, by choosing $m\geq 67w\vee 5{\cal N}_{\infty}(\lambda)w$, we have that $\beta(\lambda)\leq 2/3$, that is

Finally, note that by definition $\operatorname{Tr}(C)\leq\kappa^{2}$. ∎

Let $(\hat{l}_{i}(t))_{i=1}^{n}$ be the collection of approximate leverage scores. Let $\lambda>0$ and $P_{\lambda}$ be defined as $P_{\lambda}(i)=\hat{l}_{i}(\lambda)/\sum_{j\in N}\hat{l}_{j}(\lambda)$ for any $i\in N$ with $N=\{1,\dots,n\}$. Let $\mathfrak{I}=(i_{1},\dots,i_{m})$ be a collection of indices independently sampled with replacement from $N$ according to the probability distribution $P_{\lambda}$. Let $P_{m}$ be the projection operator on the subspace $\mathcal{H}_{m}=\operatorname{span}\{K_{x_{j}}|j\in J\}$ and $J$ be the subcollection of $\mathfrak{I}$ with all the duplicates removed. Under Assumption 3, for any $\delta>0$ the following holds with probability $1-2\delta$

when the following conditions are satisfied:

there exists a $T\geq 1$ and a $\lambda_{0}>0$ such that $(\hat{l}_{i}(t))_{i=1}^{n}$ are $T$-approximate leverage scores for any $t\geq\lambda_{0}$ (see Def. 1),

$n\,\geq\,1655\kappa^{2}+223\kappa^{2}\log\frac{2\kappa^{2}}{\delta}$,

$\lambda_{0}\vee\frac{19\kappa^{2}}{n}\log\frac{2n}{\delta}\leq\lambda\leq\lVert{C}\rVert{}$,

$m\,\geq\,334\log\frac{8n}{\delta}\,\vee\,78T^{2}{\cal N}(\lambda)\log\frac{8n}{\delta}$.

Now, considering that $\frac{q(j)}{P_{\lambda}(j)}>0$ for any $j\in J$, thus $\operatorname{ran}{}S_{n}^{*}HS_{n}=\mathcal{H}_{m}$. Therefore, by using Prop. 3 and 7, we exploit the fact that the range of $P_{m}$ is the same of $S_{n}^{*}HS_{n}$, to obtain

with $\beta(\lambda)=\lambda_{\max}\left({C}_{\lambda}^{-1/2}({C}-S_{n}^{*}HS_{n}){C}_{\lambda}^{-1/2}\right)$. Considering that the function $(1-x)^{-1}$ is increasing on $-\infty<x<1$, in order to bound $\lambda/(1-\beta(\lambda))$ we need an upperbound for $\beta(\lambda)$. Here we split $\beta(\lambda)$ in the following way,

Considering that ${{C}}_{n}$ is the linear combination of independent random vectors, for the first term we can apply Prop. 8, obtaining a bound of the form

with probability $1-\tau$, where $w=\log\frac{4\kappa^{2}}{\lambda\tau}$ (we used the fact that ${\cal N}_{\infty}(\lambda)\leq\kappa^{2}/\lambda$). Then, after dividing and multiplying by ${{C}}_{n\lambda}^{1/2}$, we split the second term $\beta_{2}(\lambda)$ as follows:

Note that $S_{n}{{C}}_{n\lambda}^{-1}S_{n}^{*}=K_{n}(K_{n}+\lambda nI)^{-1}$ indeed ${{C}}_{n\lambda}^{-1}=(S_{n}^{*}S_{n}+\lambda I)^{-1}$ and $K_{n}=nS_{n}S_{n}^{*}$. Therefore we have

Thus, if we let $U\Sigma U^{\top}$ be the eigendecomposition of $K_{n}$, we have that $(K_{n}+\lambda nI)^{-1}K_{n}=U(\Sigma+\lambda nI)^{-1}\Sigma U^{\top}$ and thus $S_{n}{{C}}_{n\lambda}^{-1}S_{n}^{*}=U(\Sigma+\lambda nI)^{-1}\Sigma U^{\top}$. In particular this implies that $S_{n}{{C}}_{n\lambda}^{-1}S_{n}^{*}=UQ_{n}^{1/2}Q_{n}^{1/2}U^{\top}$ with $Q_{n}=(\Sigma+\lambda nI)^{-1}\Sigma$. Therefore we have

where we used twice the fact that $\lVert{ABA^{*}}\rVert=\lVert{(A^{*}A)^{1/2}B(A^{*}A)^{1/2}}\rVert$ for any bounded linear operators $A,B$.

Consider the matrix $A=Q_{n}^{1/2}U^{\top}$ and let $a_{i}$ be the $i$-th column of $A$, and $e_{i}$ be the $i$-th canonical basis vector for each $i\in N$. We prove that $\lVert{a_{i}}\rVert{}^{2}=l_{i}(\lambda)$, the true leverage score, since

Noting that $\sum_{k=1}^{n}\frac{q(k)}{P_{\lambda}(k)}a_{k}a_{k}^{\top}=\sum_{i=\mathfrak{I}}\frac{1}{P_{\lambda}(i)}a_{i}a_{i}^{\top}$, we have

Moreover, by the $T$-approximation property of the approximate leverage scores (see Def. 1), we have that for all $i\in\{1,\dots,n\}$, when $\lambda\geq\lambda_{0}$, the following holds with probability $1-\delta$

Then, we can apply Prop. 9, so that, after a union bound, we obtain the following inequality with probability $1-\delta-\tau$:

where the last step follows from $\lVert{A}\rVert{}^{2}=\lVert{(K_{n}+\lambda nI)^{-1}K_{n}}\rVert{}\leq 1$ and $\operatorname{Tr}(AA^{\top})=\operatorname{Tr}({{C}}_{n\lambda}^{-1}{{C}}_{n}):=\hat{\cal N}(\lambda)$. Applying Proposition 1, we have that $\hat{\cal N}(\lambda)\leq 1.3{\cal N}(\lambda)$ with probability $1-\tau$, when $\frac{19\kappa^{2}}{n}\log\frac{n}{4\tau}\leq\lambda\leq\lVert{C}\rVert{}$ and $n\geq 405\kappa^{2}\vee 67\kappa^{2}\log\frac{\kappa^{2}}{2\tau}$. Thus, by taking a union bound again, we have

with probability $1-2\tau-\delta$ when $\lambda_{0}\vee\frac{19\kappa^{2}}{n}\log\frac{n}{\delta}\leq\lambda\leq\lVert{C}\rVert{}$ and $n\geq 405\kappa^{2}\vee 67\kappa^{2}\log\frac{2\kappa^{2}}{\delta}$. The last step is to bound $\lVert{{C}_{\lambda}^{-1/2}{{C}}_{n\lambda}^{1/2}}\rVert{}^{2}$, as follows

with $\eta=\lVert{{C}_{\lambda}^{-1/2}({{C}}_{n}-{C}){C}_{\lambda}^{-1/2}}\rVert{}$. Note that, by applying Prop. 8 we have that $\eta\leq\frac{2(\kappa^{2}+\lambda)\theta}{3\lambda n}+\sqrt{\frac{2\kappa^{2}\theta}{3\lambda n}}$ with probability $1-\tau$ and $\theta=\log\frac{8\kappa^{2}}{\lambda\tau}$. Finally, by collecting the above results and taking a union bound we have

with probability $1-4\tau-\delta=1-2\delta$ when $\lambda_{0}\vee\frac{19\kappa^{2}}{n}\log\frac{n}{\delta}\leq\lambda\leq\lVert{C}\rVert{}$ and $n\geq 405\kappa^{2}\vee 67\kappa^{2}\log\frac{2\kappa^{2}}{\delta}$. Note that, if we select $n\geq 405\kappa^{2}\vee 223\kappa^{2}\log\frac{2\kappa^{2}}{\delta}$, $m\geq 334\log\frac{8n}{\delta}$, $\lambda_{0}\vee\frac{19\kappa^{2}}{n}\log\frac{2n}{\delta}\leq\lambda\leq\lVert{C}\rVert{}$ and $\frac{78T^{2}{\cal N}(\lambda)\log\frac{8n}{\delta}}{m}\leq 1$ the conditions are satisfied and we have $\beta(\lambda)\leq 2/3$, so that

Let $\hat{\cal N}(\lambda)=\operatorname{Tr}{{C}}_{n}{{C}}_{n\lambda}^{-1}$. Under the Assumption 3, for any $\delta>0$ and $n\geq 405\kappa^{2}\vee 67\kappa^{2}\log\frac{6\kappa^{2}}{\delta}$, if $\frac{19\kappa^{2}}{n}\log\frac{n}{4\delta}\leq\lambda\leq\lVert{C}\rVert{}$, then the following holds with probability $1-\delta$,

with $q=\frac{4\kappa^{2}\log\frac{6}{\delta}}{3\lambda n}$.

Let $\tau=\delta/3$. Define $B_{n}={C}_{\lambda}^{-1/2}({C}-{{C}}_{n}){C}_{\lambda}^{-1/2}$. Choosing $\lambda$ in the range $\frac{19\kappa^{2}}{n}\log\frac{n}{4\tau}\leq\lambda\leq\lVert{C}\rVert{}$, Prop. 8 assures that $\lambda_{\max}(B_{n})\leq 1/3$ with probability $1-\tau$. Then, using the fact that ${{C}}_{n\lambda}^{-1}={C}_{\lambda}^{-1/2}(I-B_{n})^{-1}{C}_{\lambda}^{-1/2}$ (see the proof of Prop. 7) we have

Considering that for any symmetric linear operator $X:\mathcal{H}\to\mathcal{H}$ the following identity holds

and we can apply the Bernstein inequality (Prop. 10) with

An upperbound for $M$ is $M=\operatorname{Tr}(\lambda{C}_{\lambda}^{-2}C)=\operatorname{Tr}((I-{C}_{\lambda}^{-1}C){C}_{\lambda}^{-1}C)\leq\cal{N}(\lambda)$. Thus, we have

To find an upperbound for $B$, let $\cal L$ be the space of Hilbert-Schmidt operators on $\mathcal{H}$. $\cal L$ is a Hilbert space with scalar product $\left\langle{U},{V}\right\rangle_{HS}=\operatorname{Tr}{(UV^{*})}$ for all $U,V\in\cal L$. Next, note that $B=\lVert{Q}\rVert_{HS}^{2}$ where $Q=\lambda^{1/2}{C}_{\lambda}^{-1/2}B_{n}\left(I-B_{n}\right)^{-1/2}$, moreover

since $\lVert{(I-B_{n})^{-1/2}}\rVert{}^{2}=(1-\lambda_{\max}(B_{n}))^{-1}\leq 3/2$ and $(1-\sigma)^{-1}$ is increasing and positive on $[-\infty,1)$.

with probability $1-\tau$. Then, by taking a union bound for the three events we have

with $q=\frac{4\kappa^{2}\log\frac{6}{\delta}}{3\lambda n}$, and with probability $1-\delta$. Finally, if the second assumption on $\lambda$ holds, then we have $q\leq 4/57$. Noting that $n\geq 405\kappa^{2}$, and that ${\cal N}(\lambda)\geq\lVert{C{C}_{\lambda}^{-1}}\rVert{}=\frac{\lVert{C}\rVert{}}{\lVert{C}\rVert{}+\lambda}\geq 1/2$, we have that

Appendix E Proofs of main theorem

A key step to derive the proof of Theorem 1 is the error decomposition given by the following theorem, together with the probabilistic inequalities in the previous section.

Under Assumptions 1, 3, 4, let $v=\min(s,1/2)$ and $\hat{f}_{\lambda,m}$ a KRLS + generalized \Nystrom solution as in Eq. (18). Then for any $\lambda,m>0$ the error is bounded by

where ${\cal S}(\lambda,n)=\lVert{(C+\lambda I)^{-1/2}(S_{n}^{*}\widehat{y}_{n}-{{C}}_{n}f_{\mathcal{H}})}\rVert$ and ${\cal C}(m)=\lVert{(I-P_{m})(C+\lambda I)^{1/2}}\rVert^{2}$ with $P_{m}=Z_{m}^{*}(Z_{m}Z_{m}^{*})^{\dagger}Z_{m}$. Moreover $q=R(\beta^{2}\vee(1+\theta\beta))$, $\beta=\lVert{({{C}}_{n}+\lambda I)^{-1/2}({C}+\lambda I)^{1/2}}\rVert$, $\theta=\lVert{({{C}}_{n}+\lambda I)^{1/2}(C+\lambda I)^{-1/2}}\rVert$.

Let ${C}_{\lambda}={C}+\lambda I$ and ${{C}}_{n\lambda}={{C}}_{n}+\lambda I$ for any $\lambda>0$. Let $\hat{f}_{\lambda,m}$ as in Eq. (18). By Lemma 1, Lemma 2 and Lemma 3 we know that $\hat{f}_{\lambda,m}$ is characterized by $\hat{f}_{\lambda,m}=g_{\lambda m}({{C}}_{n})S_{n}^{*}\widehat{y}_{n}$ with $g_{\lambda,m}({{C}}_{n})=V(V^{*}{{C}}_{n}V+\lambda I)^{-1}V^{*}$. By using the fact that ${\mathcal{E}}(f)-{\mathcal{E}}(f_{\mathcal{H}})=\lVert{C^{1/2}(f-f_{\mathcal{H}})}\rVert^{2}_{\mathcal{H}}$ for any $f\in\mathcal{H}$ (see Prop. 1 Point 3 of [caponnetto2007optimal]), we have

Bound for the term A Multiplying and dividing by ${{C}}_{n\lambda}^{1/2}$ and ${C}_{\lambda}^{1/2}$ we have

where the last step is due to Lemma 8 and the fact that

Bound for the term B Noting that $g_{\lambda,m}({{C}}_{n}){{C}}_{n\lambda}VV^{*}=VV^{*}$, we have

Therefore, noting that by Ass. 4 we have $\lVert{{C}_{\lambda}^{-v}f_{\mathcal{H}}}\rVert_{\mathcal{H}}\leq\lVert{{C}_{\lambda}^{-s}f_{\mathcal{H}}}\rVert_{\mathcal{H}}\leq\lVert{{C}^{-s}f_{\mathcal{H}}}\rVert_{\mathcal{H}}\leq R$, then, by reasoning as in A, we have

where in the second step we applied the decomposition of $I-g_{\lambda m}({{C}}_{n}){{C}}_{n}$.

Bound for the term B.1 Since $VV^{*}$ is a projection operator, we have that $(I-VV^{*})=(I-VV^{*})^{s}$, for any $s>0$, therefore

By applying Cordes inequality (Prop. 4) to $\lVert{(I-VV^{*}){C}_{\lambda}^{v}}\rVert$ we have,

where the first step is obtained multipling and dividing by ${{C}}_{n\lambda}^{v}$, the second step by applying Cordes inequality (see Prop. 4), the third step by Prop. 6. ∎

For any $\delta>0$, let $n\,\geq\,1655\kappa^{2}+223\kappa^{2}\log\frac{6\kappa^{2}}{\delta}$, let $\frac{19\kappa^{2}}{n}\log\frac{6n}{\delta}\leq\lambda\leq\lVert{C}\rVert{}$ and define

Under the assumptions of Thm. 2 and Assumption 2, 3, if one of the following two conditions hold

$T$-approximate leverage scores, for any $t\geq\frac{19\kappa^{2}}{n}\log\frac{12n}{\delta}$ (see Def. 1),

resampling probabilities $P_{t}$ where $t={\cal C}_{\textrm{ALS}}(m)$ (see Sect. 2),

then the following holds with probability $1-\delta$

where ${\cal C}(m)={\cal C}_{\rm pl}(m)$ in case of plain \Nystrom and ${\cal C}(m)={\cal C}_{\rm ALS}(m)$ in case of ALS \Nystrom.

In order to get explicit bounds from Thm. 2, we have to control four quantities that are $\beta,\theta,{\cal S}(\lambda,n)$ and ${\cal C}(m)$. In the following we bound such quantities in probability and then take a union bound. Let $\tau=\delta/3$. We can control both $\beta$ and $\theta$, by bounding $b(\lambda)=\lVert{{C}_{\lambda}^{-1/2}({{C}}_{n}-C){C}_{\lambda}^{-1/2}}\rVert$. Indeed, by Prop. 7, we have that $\beta\leq 1/(1-b(\lambda))$, while

Exploiting Prop. 8, with the fact that ${\cal N}(\lambda)\leq{\cal N}_{\infty}(\lambda)\leq\frac{\kappa^{2}}{\lambda}$ and $\operatorname{Tr}C\leq\kappa^{2}$, we have that $b(\lambda)\leq\frac{2(\kappa^{2}+\lambda)w}{3\lambda n}+\sqrt{\frac{2w\kappa^{2}}{\lambda n}}$ for $w=\log\frac{4\kappa^{2}}{\tau\lambda}$ with probability $1-\tau$. Simple computations show that with $n$ and $\lambda$ as in the statement of this corollary, we have $b(\lambda)\leq 1/3$. Therefore $\beta\leq 1.5$, while $\theta\leq 1.16$ and $q=R(\beta^{2}\vee(1+\theta\beta))<2.75R$ with probability $1-\tau$. Next, we bound ${\cal S}(\lambda,n)$. Here we exploit Lemma 4 which gives, with probability $1-\tau$,

To bound ${\cal C}(m)$ for plain \Nystrom, Lemma 6 gives ${\cal C}(m)\leq 3t$ with probability $1-\tau$, for a $t>0$ such that $(67\vee 5{\cal N}_{\infty}(t))\log\frac{4\kappa^{2}}{t\tau}\leq m$. In particular, we choose $t={\cal C}_{\rm pl}(m)$ to satisfy the condition. Next we bound ${\cal C}(m)$ for ALS \Nystrom. Using Lemma 7 with $\lambda_{0}=\frac{19\kappa^{2}}{n}\log\frac{2n}{\tau}$, we have ${\cal C}(m)\leq 3t$ with probability $1-\tau$ under some conditions on $t,m,n$, on the approximate leverage scores and on the resampling probability. Here again the requirement on $n$ is satisfied by the hypotesis on $n$ of this proposition, while the condition on the approximate leverage scores and on the resampling probabilities are satisfied by conditions (a), (b) of this proposition. The remaining two conditions are $\frac{19\kappa^{2}}{n}\log\frac{4n}{\tau}\leq t\leq\lVert{C}\rVert{}$ and $(334\vee 78T^{2}{\cal N}(t))\log\frac{16n}{\tau}\leq m$. They are satisfied by choosing $t={\cal C}_{\rm ALS}(m)$ and by assuming that $m\geq 334\log\frac{16n}{\tau}$. Finally, the proposition is obtained by substituting each of the four quantities $\beta,\theta,{\cal S}(\lambda,n),{\cal C}(m)$ with the corresponding upperbounds in Eq. (21), and by taking the union bounds on the associated events. ∎

By exploiting the results of Prop. 2, obtained from the error decomposition of Thm. 2 we have that

with probability $1-\delta$, under conditions on $\lambda,m,n$, on the resampling probabilities and on the approximate leverage scores. The last is satisfied by condition (a) in this theorem. The conditions on $\lambda,n$ are $n\geq 1655\kappa^{2}+223\kappa^{2}\log\frac{6\kappa^{2}}{\delta}$ and $\frac{19\kappa^{2}}{n}\log\frac{12n}{\delta}\leq\lambda\leq\lVert{C}\rVert{}$. If we assume that $n\geq 1655\kappa^{2}+223\kappa^{2}\log\frac{6\kappa^{2}}{\delta}+\left(\frac{38p}{\lVert{C}\rVert}\log\frac{114\kappa^{2}p}{\lVert{C}\rVert\delta}\right)^{p}$ we satisfy the condition on $n$ and at the same time we are sure that $\lambda=\lVert{C}\rVert n^{-1/(2v+\gamma+1)}$ satisfies the condition on $\lambda$. In the plain \Nystrom case, if we assume that $m\geq 67\log\frac{12\kappa^{2}}{\lambda\delta}+5{\cal N}_{\infty}(\lambda)\log\frac{12\kappa^{2}}{\lambda\delta}$, then ${\cal C}(m)={\cal C}_{\rm pl}(m)\leq\lambda$. In the ALS \Nystrom case, if we assume that $m\geq(334\vee 78T^{2}{\cal N}(\lambda))\log\frac{48n}{\delta}$ the condition on $m$ is satisfied, then ${\cal C}(m)={\cal C}_{\rm ALS}(m)\leq\lambda$, moreover the conditions on the resampling probabilities is satisfied by condition (b) of this theorem. Therefore, by setting $\lambda=\lVert{C}\rVert n^{-1/(2v+\gamma+1)}$ in Eq. (23) and considering that ${\cal N}_{\infty}(\lambda)\leq\kappa^{2}\lambda^{-1}$ we easily obtain the result of this theorem. ∎

The following lemma is a technical result needed in the error decomposition (Thm. 2).

For any $\lambda>0$, let $V$ be such that $V^{*}V=I$ and ${{C}}_{n}$ be a positive self-adjoint operator. Then, the following holds,

Let ${{C}}_{n\lambda}={{C}}_{n}+\lambda I$ and $g_{\lambda m}({{C}}_{n})=V(V^{*}{{C}}_{n}V+\lambda I)^{-1}V^{*}$, then

and therefore the only possible values for $\lVert{{{C}}_{n\lambda}^{1/2}g_{\lambda m}({{C}}_{n}){{C}}_{n\lambda}^{1/2}}\rVert$ are or $1$. ∎

Appendix F Auxiliary results

Let $\mathcal{H},\mathcal{K},{\cal F}$ three separable Hilbert spaces, let $Z:\mathcal{H}\to\mathcal{K}$ be a bounded linear operator and let $P$ be a projection operator on $\mathcal{H}$ such that $\operatorname{ran}{P}=\overline{\operatorname{ran}{Z^{*}}}$. Then for any bounded linear operator $F:{\cal F}\to\mathcal{H}$ and any $\lambda>0$ we have

First of all note that $\lambda(Z^{*}Z+\lambda I)^{-1}=I-Z^{*}(ZZ^{*}+\lambda I)^{-1}Z$, that $Z=ZP$ and that $\lVert{Z^{*}(ZZ^{*}+\lambda I)^{-1}Z}\rVert\leq 1$ for any $\lambda>0$. Then for any $v\in\mathcal{H}$ we have

therefore $P-Z^{*}(ZZ^{*}+\lambda I)^{-1}Z$ is a positive operator, and $(I-Z^{*}(ZZ^{*}+\lambda I)^{-1}Z)-(I-P)$ too. Now we can apply Prop. 5. ∎

Let $A,B$ two positive semidefinite bounded linear operators on a separable Hilbert space. Then

Let $\mathcal{H},\mathcal{K},{\cal F},{\cal G}$ be three separable Hilbert spaces and let $X:\mathcal{H}\to\mathcal{K}$ and $Y:\mathcal{H}\to{\cal F}$ be two bounded linear operators. For any bounded linear operator $Z:{\cal G}\to\mathcal{H}$, if $Y^{*}Y-X^{*}X$ is a positive self-adjoint operator then $\lVert{XZ}\rVert{}\leq\lVert{YZ}\rVert{}$.

If $Y^{*}Y-X^{*}X$ is a positive operator then $Z^{*}(Y^{*}Y-X^{*}X)Z$ is positive too. Thus for all $f\in\mathcal{H}$ we have that $\left\langle{f},{(Q-P)f}\right\rangle{}\geq 0$, where $Q=Z^{*}Y^{*}YZ$ and $P=Z^{*}X^{*}XZ$. Thus, by linearity of the inner product, we have

Let $\mathcal{H},\mathcal{K}$ be two separable Hilbert spaces, let $A:\mathcal{H}\to\mathcal{H}$ be a positive linear operator, $V:\mathcal{H}\to\mathcal{K}$ a partial isometry and $B:\mathcal{K}\to\mathcal{K}$ a bounded operator. Then $\lVert{A^{r}VBV^{*}A^{s}}\rVert\leq\lVert{(V^{*}AV)^{r}B(V^{*}AV)^{s}}\rVert$, for all $0\leq r,s\leq 1/2$.

By Hansen’s inequality (see [hansen1980operator]) we know that $(V^{*}AV)^{2t}-V^{*}A^{2t}V$ is positive selfadjoint operator for any $0\leq t\leq 1/2$, therefore we can apply Prop. 5 two times, obtaining