You are an expert at summarizing long articles. Proceed to summarize the following text: 
we study a problem of estimation of a symmetric kernel @xmath13 defined on a large weighted graph with a vertex set @xmath1 and @xmath14 based on a finite number of noisy linear measurements of @xmath10 . for simplicity , assume that these are the measurements of randomly picked entries of @xmath15 matrix @xmath16 , which is a standard sampling model in matrix completion . more precisely , let @xmath17 be @xmath5 independent copies of a random triple @xmath18 , where @xmath19 are independent random vertices sampled from the uniform distribution @xmath20 in @xmath1 , and @xmath21 is a `` measurement '' of the kernel @xmath10 at a random location @xmath22 in the sense that @xmath23 . in what follows , we assume that , for some constant @xmath24 , @xmath25 a.s . , which implies that @xmath26 . the target kernel @xmath10 is to be estimated based on its i.i.d . measurements @xmath17 . we would like to study this problem in the case when the target kernel @xmath10 is , on the one hand , `` low rank '' [ i.e. , @xmath27 is relatively small compared to @xmath28 , and on the other hand , it is `` smooth '' in the sense that its `` sobolev - type norm '' is not too large . discrete versions of sobolev norms can be defined for functions and kernels on weighted graphs in terms of their graph laplacians . the problem of estimation of smooth low - rank kernels is of importance in a number of applications , such as learning kernels representing and predicting similarities between objects , various classification problems in large complex networks ( e.g. , edge sign prediction ) as well as matrix completion problems in the design of recommender systems ( collaborative filtering ) . our main motivation , however , is mostly theoretical : we would like to explore to which extent taking into account smoothness of the target kernel could improve the existing methods of low rank recovery . we introduce some notation used throughout the paper . let @xmath29 be the linear space of _ symmetric kernels _ @xmath30 , @xmath31 ( or , equivalently , symmetric @xmath15 matrices with real entries ) . given @xmath32 , we use the notation @xmath33 for the rank of @xmath34 and @xmath35 for its trace . for two functions @xmath36 , @xmath37 . suppose that @xmath38 is the spectral representation of @xmath34 with @xmath39 , @xmath40 being nonzero eigenvalues of @xmath34 repeated with their multiplicities and @xmath41 being the corresponding orthonormal eigenfunctions ( obviously , there are multiple choices of @xmath42s in the case of repeated eigenvalues ) . we will define @xmath43 as @xmath44 and the support of @xmath34 as @xmath45 . for @xmath46 , define the schatten @xmath47-norm of @xmath34 as @xmath48 where @xmath49 . for @xmath50 , @xmath51 is also called the nuclear norm and , for @xmath52 , @xmath53 is called the hilbert  schmidt or frobenius norm . this norm is induced by the hilbert schmidt inner product which will be denoted by @xmath54 . the operator norm of @xmath34 is defined as @xmath55 . by @xmath54 and the corresponding euclidean norm by @xmath56 . ] let @xmath57 be the distribution of random couple @xmath22 . the @xmath58-norm of kernel @xmath34 , @xmath59 is naturally related to the sampling model studied in the paper , and it will be used to measure the estimation error . denote by @xmath60 the corresponding inner product . since @xmath20 is the uniform distribution in @xmath1 , @xmath61 and @xmath62 . in what follows , it will be often more convenient to use these rescaled versions rather than the actual hilbert schmidt norm or inner product .    we will denote by @xmath63 the canonical orthonormal basis of the space @xmath64 . based on this basis , one can construct matrices @xmath65 . if @xmath66 is an arbitrary ordering of the vertices in @xmath1 , then @xmath67 is an orthonormal basis of the space @xmath68 of symmetric matrices with hilbert schmidt inner product .    in standard matrix completion problems , @xmath1 is a finite set with no further structure ( i.e. , the set of edges of the graph or the weight matrix are not specified ) . in the noiseless matrix completion problems , the target matrix @xmath10 is to be recovered from the measurements @xmath17 , where @xmath69 . the following method is based on nuclear norm minimization over the space of all matrices that `` agree '' with the data @xmath70 it has been studied in detail in the recent literature ; see @xcite and references therein . clearly , there are low rank matrices @xmath10 that can not be recovered based on a random sample of @xmath5 entries unless @xmath5 is comparable with the total number of the entries of the matrix . for instance , for given @xmath71 , let @xmath72 . then , @xmath73 . however , the probability that the only two nonzero entries of @xmath10 are not present in the sample is @xmath74 , and it is close to @xmath75 when @xmath76 . in this case , the matrix @xmath10 can not be recovered . so - called _ low coherence _ assumptions have been developed to define classes of `` generic '' matrices that are not `` low rank '' and `` sparse '' at the same time and for which noiseless low rank recovery is possible with a relatively small number of measurements . for a linear subspace @xmath77 , let @xmath78 be the orthogonal complement of @xmath79 and let @xmath80 be the orthogonal projector onto the subspace @xmath79 . denote @xmath81 , @xmath82 . a _ coherence coefficient _ is a constant @xmath83 such that @xmath84 \\[-8pt ] \nonumber \bigl |\bigl\langle\operatorname { sign}(s_{\ast})e_u , e_v\bigr \rangle\bigr|^2 & \leq&\frac{\nu r}{m^2 } , \qquad u , v\in v\end{aligned}\ ] ] ( it is easy to see that @xmath85 can not be smaller than @xmath75 ) . the following highly nontrivial result is essentially due to candes and tao @xcite ( a version stated here is due to gross  @xcite and it is an improvement of the initial result of candes and tao ) . it shows that target matrices of `` low coherence '' ( for which @xmath85 is a relatively small constant ) can be recovered exactly using the nuclear norm minimization algorithm ( [ nucemin ] ) provided that the number of observed entries is of the order @xmath86 ( up to a log factor ) . [ gross ] suppose conditions ( [ cohera ] ) hold for some @xmath83 . then , there exists a numerical constant @xmath87 such that , for all @xmath88 , @xmath89 with probability at least @xmath90 .    in the case of noisy matrix completion , a matrix version of lasso is based on a trade - off between fitting the target matrix to the data using least squares and minimizing the nuclear norm @xmath91.\ ] ] this method and its modifications have been studied by a number of authors ; see  @xcite . the following low - rank oracle inequality was proved in  @xcite ( theorem 4 ) for a `` linearized version '' of the matrix lasso estimator  @xmath92 . assume that , for some constant @xmath24 , @xmath25 a.s . let @xmath93 and suppose that @xmath94 then , there exists a constant @xmath87 such that with probability at least @xmath95 @xmath96.\ ] ] in particular , @xmath97 very recently , the last bound was proved in  @xcite for the matrix lasso estimator ( [ lsnuce ] ) itself in the case when the domain of optimization problem is @xmath98 , where @xmath99 ; in fact , both  @xcite and  @xcite dealt with the case of rectangular matrices .    in the current paper , we are more interested in the case when the target kernel  @xmath10 is defined on the set @xmath1 of vertices of a weighted graph @xmath100 with a symmetric matrix @xmath101 of nonnegative weights . this allows one to define the notion of graph laplacian and to introduce discrete sobolev norms characterizing smoothness of functions on @xmath1 as well as symmetric kernels on @xmath102 . denote @xmath103 it is common in graph theory to call @xmath104 the degree of vertex @xmath105 . let @xmath106 be the diagonal @xmath15 matrix ( kernel ) with the degrees of vertices on the diagonal ( it is assumed that the vertices of the graph have been ordered in an arbitrary , but fixed way ) . the laplacian of the weighted graph @xmath107 is defined as @xmath108 . denote @xmath54 the canonical euclidean inner product in the @xmath109-dimensional space @xmath64 of functions @xmath110 and let @xmath56 be the corresponding norm . it is easy to see that @xmath111 implying that @xmath112 is a symmetric nonnegatively definite linear transformation . in a special case of a usual graph @xmath113 with vertex set @xmath1 and edge set @xmath114 , one defines @xmath115 if and only if @xmath116 ( i.e. , vertices @xmath105 and @xmath117 are connected with an edge ) and @xmath118 otherwise . in this case , @xmath104 is the number of edges incident to the vertex @xmath105 and @xmath119 the notion of graph laplacian allows one to define discrete sobolev norms @xmath120 for functions on the vertex set of the graph and thus to describe their smoothness on the graph . given a symmetric kernel @xmath121 , one can also describe its smoothness in terms of the norms @xmath122 . suppose @xmath34 has the following spectral representation : @xmath123 where @xmath124 are the eigenvalues of @xmath34 ( repeated with their multiplicities ) and @xmath125 are the corresponding orthonormal eigenfunctions in @xmath64 , then @xmath126 basically , it means that the smoothness of the kernel @xmath34 depends on the smoothness of its eigenfunctions . in what follows , we will often use rescaled versions of sobolev norms , @xmath127    it will be convenient for our purposes to fix @xmath128 and to define a nonnegatively definite symmetric kernel @xmath129 . we will characterize the smoothness of a kernel @xmath130 by the squared sobolev - type norm @xmath131 . the kernel @xmath132 will be fixed throughout the paper , and its spectral properties are crucial in our analysis . to the graph and its laplacian will be of little importance allowing , possibly , other interpretations of the problem . ] assume that @xmath132 has the following spectral representation @xmath133 where @xmath134 are the eigenvalues repeated with their multiplicities , and @xmath135 are the corresponding orthonormal eigenfunctions ( of course , there is a multiple choice of @xmath136 in the case of repeated eigenvalues ) . let @xmath137 . we will assume in what follows that , for some constant @xmath138 , @xmath139 for all @xmath140 . it will be also convenient to set @xmath141 . let @xmath142 and @xmath143 . it is easy to show ( see the proof of theorem  [ lsupth ] below ) that kernel @xmath10 can be approximated by the following kernel : @xmath144 with the approximation error @xmath145 note that the kernel @xmath146 can be viewed as an @xmath147 matrix ( represented in the basis of eigenfunctions @xmath148 ) and @xmath149 , so , one needs @xmath150 parameters to characterize such matrices . thus , one can expect , that such a kernel can be estimated , based on @xmath5 linear measurements , with the squared @xmath58-error of the order @xmath151 . taking into account the bound on the approximation error ( [ apprerr ] ) and optimizing with respect to @xmath152 , it would be also natural to expect the following error rate in the problem of estimation of the target kernel @xmath153 @xmath154.\ ] ] we will show that such a rate is attained ( up to constants and log factors ) for a version of least squares method with a nonconvex complexity penalty ; see section  [ sectlsnonconvex ] . this method is not computationally tractable , so , we also study another method , based on convex penalization with a combination of nuclear norm and squared sobolev type norm , and show that the rates are attained for such a method , too , provided that the target matrix satisfies a version low coherence assumption with respect to the basis of eigenfunctions of @xmath132 . more precisely , we will prove error bounds involving so called _ coherence function _ @xmath155 , that characterizes the relationship between the kernel @xmath132 defining the smoothness and the target kernel @xmath10 ; see section  [ sectlsconvex ] for more details ; see also  @xcite for similar results in the case of `` linearized least squares '' estimator with double penalization . finally , we prove minimax lower bounds on the error rate that are roughly of the order @xmath156 $ ] ( subject to some extra conditions and with additional terms ; see section  [ sectlowerbound ] ) . in typical situations , this expression is , up to a constant , of the same order as the upper bound ( [ upperbd ] ) . for instance , if @xmath157 for some @xmath158 , then the minimax error rate of estimation of the target kernel @xmath10 is of the order @xmath159 ( up to log factors ) . when @xmath109 is sufficiently large , the term @xmath160 will be dropped from the minimum , and we end up with a nonparametric convergence rate controlled by the smoothness parameter @xmath161 and the rank @xmath162 of the target matrix @xmath10 ( the dependence on @xmath109 in the first two terms of the minimum is only in the log factors ) . the focus of the paper is on the matrix completion problems with uniform random design , but it is very straightforward to extend the results of the following sections to sampling models with more general design distributions discussed in the literature on low rank recovery ( such as , e.g. , the models of random linear measurements studied in @xcite ) . it is also not hard to replace the range @xmath163 of the response variable @xmath164 by the standard deviation of the noise in the upper and lower bounds obtained below . this is often done in the literature on low - rank recovery , and it can be easily extended to the framework discussed in the paper by modifying our proofs . we have not discussed this in the paper due to the lack of space . in this section , we derive minimax lower bounds on the @xmath165-error of an arbitrary estimator @xmath92 of the target kernel @xmath10 under the assumptions that the response variable @xmath164 is bounded by a constant @xmath24 , the rank of @xmath10 is bounded by @xmath166 and its sobolev norm @xmath167 is bounded by @xmath168 . more precisely , given @xmath169 and @xmath170 , denote by @xmath171 the set of all symmetric kernels @xmath30 such that @xmath172 and . given @xmath173 and @xmath24 , let @xmath174 be the set of all probability distributions of @xmath18 such that @xmath22 is uniformly distributed in @xmath102 , @xmath25 a.s . and @xmath23 , where @xmath175 . for @xmath176 , denote @xmath177 . recall that @xmath178 are the eigenfunctions of @xmath132 orthonormal in the space @xmath179 . then @xmath180 are orthonormal in  @xmath181 . we will obtain minimax lower bounds for classes of distributions @xmath182 in two different cases . define @xmath183 in the first case , we assume that , for some ( relatively large ) value of @xmath184 , the quantity @xmath185 is not too large . roughly , it means that most of the components of vectors @xmath186 are uniformly small , say , @xmath187 in other words , the @xmath15 matrix @xmath188 is `` dense , '' so we refer to this case as a _ `` dense case . '' _ the opposite case is when this matrix is _ `` sparse . '' _ its `` sparsity '' will be characterized by the quantity @xmath189 which , in this case , should be relatively small . a typical example is the case when basis of eigenfunctions @xmath190 coincides with the canonical basis @xmath63 of @xmath64 ( then , @xmath191 ) . denote @xmath192 . in the _ dense case _ , the following theorem holds . [ lowerbound ] define @xmath193.\ ] ] there exist constants @xmath194 such that @xmath195 where the infimum is taken over all the estimators @xmath196 based on @xmath5 i.i.d . copies of @xmath18 . in fact , it will follow from the proof that , if @xmath197 ( i.e. , the smallest nonzero eigenvalue of @xmath132 is not too large ) , then the maximum in the definition of @xmath198 can be extended to all @xmath152 . [ lowerboundcorr ] let @xmath199.\ ] ] there exist constants @xmath194 such that @xmath200    take @xmath201 in the statement of theorem  [ lowerbound ] and observe that @xmath202 and @xmath203 . it is easy to check that @xmath204 . it is obvious that one can replace the quantity @xmath205 in theorem  [ lowerbound ] [ or the quantity @xmath206 in corollary [ lowerboundcorr ] ] by the following smaller quantity : @xmath207,\ ] ] where @xmath208\wedge m. $ ] moreover , denote @xmath209 it is straightforward to check that @xmath210 = \frac{a^2(r\wedge\bar l)\bar l}{n } \vee\frac{\rho ^2}{\lambda_{\bar l+1}}\ ] ] and , if @xmath211 , then @xmath212    suppose that , for some @xmath158 , @xmath213 ( in particular , it means that @xmath214 and @xmath215 ) . then , an easy computation shows that @xmath216 let @xmath201 and take @xmath217\wedge m. $ ] the condition @xmath211 is satisfied , for instance , when either @xmath218 , or @xmath219 , where @xmath220 is a small enough constant ( this , essentially , means that @xmath5 is sufficiently large ) . under either of these conditions , we get the following expression for a minimax lower bound : @xmath221    we now turn to the _ sparse case_.    [ lowerboundsparse ] let @xmath222.\ ] ] there exist constants @xmath194 such that @xmath223    it will be clear from the upper bounds of section  [ sectlsnonconvex ] ( see the remark after theorem  [ lsupth ] ) that , at least in a special case when @xmath148 coincides with the canonical basis of @xmath64 , the additional term @xmath224 is correct ( up to a log factor ) . at the same time , most likely , the `` third terms '' of the bounds of theorem  [ lowerbound ] ( in the dense case ) and theorem  [ lowerboundsparse ] ( in the sparse case ) have not reached their final form yet . a more sophisticated construction of `` well separated '' subsets of @xmath174 might be needed to achieve this goal . the main difficulty in the proof given below is related to the fact that we have to impose constraints , on the one hand , on the entries of the target matrix represented in the canonical basis and , on the other hand , on the soblolev type norm @xmath225 ( for which it is convenient to use the representation in the basis of eigenfunctions of @xmath132 ) . due to this fact , we are using the last representation in our construction , and we have to use an argument based on the properties of rademacher sums to ensure that the entries of the matrix represented in the canonical basis are uniformly bounded by @xmath163 . this is the reason why the `` third terms '' occur in the bounds of theorems [ lowerbound ] and  [ lowerboundsparse ] . in this case , when the constraints are only on the norm @xmath226 and on the variance of the noise and there are no constraints on @xmath227 , it is much easier to prove the lower bound of the order @xmath228 $ ] without any additional terms . note , however , that the condition @xmath229 is of importance in the following sections to obtain the upper bounds for penalized least squares estimators that match the lower bounds up to log factors . proof of theorem  [ lowerbound ] the proof relies on several well - known facts stated below . in what follows , @xmath230 denotes kullback  leibler divergence between two probability measures @xmath231 defined on the same space and such that @xmath232 ( i.e. , @xmath85 is absolutely continuous with respect to @xmath233 ) . we will denote by @xmath234 the @xmath5-fold product measure @xmath235 . the following proposition is a version of theorem 2.5 in  @xcite . [ kbound ] let @xmath236 be a finite set of distributions of @xmath18 such that the following assumptions hold :    there exists @xmath237 such that for all @xmath238 , @xmath239 ;    there exists @xmath240 such that @xmath241    for all @xmath242 , @xmath243 . then , there exists a constant @xmath244 such that @xmath245    we will also use varshamov  gilbert bound ( see  @xcite , lemma 2.9 , page  104 ) , sauer s lemma ( see  @xcite , page 39 ) and the following elementary bound for rademacher sums ( @xcite , page 21 ) : for all @xmath184 , @xmath246 where @xmath247 are i.i.d . rademacher random variables ( i.e. , @xmath248 with probability @xmath249 and @xmath250 with the same probability ) . we will start the proof with constructing a `` well separated '' subset @xmath236 of the class of distributions @xmath251 that will allow us to use proposition  [ kbound ] . fix @xmath252 , @xmath253 and @xmath254 . denote @xmath255 , l''=l - l'$ ] . first assume that @xmath256 . denote @xmath257 , where @xmath258 or @xmath259 . let @xmath260 ( so , @xmath261 is the class of all @xmath262 matrices with entries @xmath263 or @xmath264 ) . given @xmath265 , let @xmath266 be the @xmath267 matrix that consists of @xmath268 $ ] blocks @xmath269 and the last block @xmath270 , where @xmath271r$ ] and @xmath272 is the @xmath273 zero matrix . finally , define the following symmetric @xmath15 matrix : @xmath274 now , given @xmath275 , define a symmetric kernel @xmath276 , @xmath277 it is easy to see that @xmath278 \\[-8pt ] \nonumber k_{\sigma}^{\prime } ( u , v)&= & \kappa\sum _ { i=1}^{l'}\sum_{j=1}^r \sigma_{ij}\phi_i(u)\sum_{k=0}^{[l''/r]-1 } \phi_{l'+rk+j}(v).\end{aligned}\ ] ]    let @xmath279 we will show that , if @xmath280 is sufficiently small ( its precise value to be specified later ) , then the set @xmath281 contains at least three quarters of the points of the combinatorial cube @xmath282 . to this end , define @xmath283 where @xmath284 is a random vector with i.i.d . rademacher components . assume , in addition , that @xmath285 and @xmath22 are independent . it is enough to show that @xmath286 with probability at least @xmath287 . we have @xmath288 we will use bound ( [ rademach ] ) to control @xmath289 [ recall that @xmath290 is a rademacher sum ] . denote @xmath291 - 1}\phi_{l'+rk+j}(v ) \biggr)^2 . \ ] ] observe that @xmath292 where @xmath293 and we used the bound @xmath294 - 1 } \phi_{l'+rk+j}(v ) \biggr)^2\leq \frac{l''}{r } \sum _ { k=0}^{[l''/r]-1}\phi_{l'+rk+j}^2(v).\ ] ] thus , applying ( [ rademach ] ) to the rademacher sum @xmath295 , we get @xmath296 given @xmath297 $ ] , denote @xmath298 for @xmath152 . this yields @xmath299 substituting the last bound into ( [ ogogo ] ) , we get @xmath300 now , to get @xmath301 , it is enough to take @xmath302    next observe that @xmath303}\pmatrix{l'r \cr k}.\ ] ] it follows from sauer s lemma that there exists a subset @xmath304 with @xmath305 + 1 $ ] and such that @xmath306 , where @xmath307 , @xmath308 since @xmath253 , we have @xmath309 and @xmath310 . we can now apply varshamov gilbert bound to the combinatorial cube @xmath311 to prove that there exists a subset @xmath312 such that @xmath313 and , for all @xmath314 , @xmath315 it is now possible to choose a subset @xmath316 of @xmath281 such that @xmath317 and @xmath318 . then , we have @xmath319 and @xmath320 for all @xmath321 . we are now in a position to define the set of distributions @xmath236 . for @xmath322 , denote by @xmath323 the distribution of @xmath18 such that @xmath22 is uniform in @xmath102 and the conditional distribution of @xmath164 given @xmath22 is defined as follows : @xmath324    since @xmath325 for all @xmath322 , we have @xmath326,\sigma\in\lambda$ ] . denote @xmath327 . for @xmath328 , we have @xmath329 note that @xmath330 ; see the definitions of @xmath331 and @xmath332 . moreover , we have @xmath333 and @xmath334 - 1 } \phi_i\otimes\phi_{l'+rk+j}\\ & & \hspace*{2pt } { } + \kappa\sum _ { i=1}^{r}\sum_{j=1}^{l ' } \sigma_{ji}\sum_{k=0}^{[l''/r]-1 } \phi_{l'+rk+i}\otimes\phi_j \biggr\|_2 ^ 2 \\ & \leq & 2 \kappa^2 l'r \bigl[l''/r \bigr]\leq\kappa^2 l^2.\end{aligned}\ ] ] therefore , @xmath335 so , we have @xmath336 provided that @xmath337 we can conclude that , for all @xmath338 , @xmath339 provided that @xmath280 satisfies conditions  ( [ kappa1 ] ) and ( [ kappa3 ] ) . since also @xmath25 , we have that @xmath340 . next we check that @xmath236 satisfies the conditions of proposition [ kbound ] . it is easy to see that , for all @xmath341 and @xmath342 using the elementary inequality @xmath343 and the fact that @xmath326,\sigma\in\lambda$ ] , we get that @xmath344 a simple computation based on the definition of @xmath345 easily yields that @xmath346\leq8\kappa ^2 l ' l '' \leq4 \kappa^2 l^2.\ ] ] thus , for the @xmath5-fold product - measures @xmath347 , we get @xmath348 for a fixed @xmath322 , this yields @xmath349 \\[-8pt ] \nonumber & \leq&\frac{1}{10 } \log\bigl(\operatorname { card}\bigl(\lambda ' \bigr)-1\bigr),\end{aligned}\ ] ] provided that @xmath350    it remains to use ( [ hemming ] ) and the definition of kernels @xmath331 to bound from below the squared distance @xmath351 for @xmath352 , @xmath353 \geq\frac{1}{64 } \kappa^2 \frac{l^2}{m^2}.\ ] ] since @xmath354 , this implies that @xmath355    in view of ( [ kappa1 ] ) , ( [ kappa2 ] ) and ( [ kappa3 ] ) , we now take @xmath356 with this choice of @xmath280 , @xmath357 . in view of ( [ l2below ] ) and ( [ klabove ] ) , we can use proposition  [ kbound ] to get @xmath358 \\[-8pt ] \nonumber & & \qquad\geq \inf_{\hat s } \sup_{p\in{\cal p}}{\mathbb p}_p \bigl\ { \|\hat s - s_p\|_{l_2(\pi^2)}^2\geq c_1 \delta_n \bigr\ } \geq c_2,\end{aligned}\ ] ] where @xmath359 and @xmath194 are constants .    in the case when @xmath360 , bound ( [ knc ] ) still holds with @xmath361 the proof is an easy modification of the argument in the case when @xmath256 . for @xmath360 , the construction becomes simpler : namely , we define @xmath362 where @xmath363 , and , based on this , redefine kernels @xmath364 . the proof then goes through with minor simplifications . thus , in both cases @xmath365 and @xmath256 , ( [ knc ] ) holds with @xmath366 this is true under the assumption that @xmath253 . note also that @xmath367 . thus , we can replace @xmath368 by the upper bound @xmath369 in the definition of @xmath370 . we can now choose @xmath371 that maximizes @xmath370 to get bound ( [ knc ] ) with @xmath372 . this completes the proof in the case when @xmath373 and @xmath374 . if @xmath375 , it is easy to use the condition @xmath376 and to show that @xmath377 where @xmath378 is a constant depending only on @xmath379 . this completes the proof in the remaining case . proof of theorem  [ lowerboundsparse ] the only modification of the previous proof is to replace bound ( [ lr - d ] ) by @xmath380 - 1}\phi_{l'+rk+j}(v ) ) ^2\leq d\sum_{k=0}^{[l''/r]-1}\phi_{l'+rk+j}^2(v ) . $ ] then , the outcome of the next several lines of the proof is that @xmath301 provided that [ instead of ( [ kappa1 ] ) ] @xmath381 as a result , at the end of the proof , we get that ( [ knc ] ) holds with @xmath382 it remains to observe that @xmath383 , which follows from the fact that @xmath384 and to take @xmath201 to complete the proof . in this section , we derive upper bounds on the squared @xmath165-error of the following least squares estimator of the target matrix @xmath10 : @xmath385 where @xmath386 , @xmath387 here @xmath388 denotes a truncation of kernel @xmath389 if @xmath390 , @xmath391 if @xmath392 and @xmath393 if @xmath394 . note that the kernels in the class @xmath395 are symmetric and @xmath396 . note also that the sets @xmath395 , @xmath397 and optimization problem ( [ leastsquare ] ) are not convex . we will prove the following result under the assumption that @xmath25 a.s . recall the definition of the class of kernels @xmath171 in section  [ sectlowerbound ] . [ lsupth ] there exist constants @xmath398 such that , for all @xmath93 , with probability at least @xmath95 , @xmath399 \\[-8pt ] \nonumber & & { } + c \biggl(\frac{a^2 ( r\wedge l)l}{n}\log \biggl(\frac{a n m}{(r\wedge l)l } \biggr)+ \frac{a^2 t}{n } \biggr).\end{aligned}\ ] ] in particular , for some constants @xmath400 , for @xmath175 and for all @xmath93 , with probability at least @xmath95 , @xmath401.\ ] ]    without loss of generality , assume that @xmath402 this would imply the general case by a simple rescaling of the problem . we will use a version of well - known bounds for least squares estimators over uniformly bounded function classes in terms of rademacher complexities . specifically , consider the following least squares estimator : @xmath403 where @xmath404 are i.i.d . copies of a random couple @xmath405 in @xmath406 , @xmath407 being a measurable space , @xmath408 a.s . , @xmath409 being a class of measurable functions on @xmath410 uniformly bounded by @xmath75 . the goal is to estimate the regression function @xmath411 . define localized rademacher complexity @xmath412 where @xmath20 is the distribution of @xmath413 and @xmath414 is the rademacher process , @xmath415 being a sequence of i.i.d . rademacher random variables independent of @xmath416 . denote @xmath417 and @xmath418 the next result easily follows from theorem 5.2 in  @xcite :    [ regr ] there exist constants @xmath194 such that , for all @xmath93 , with probability at least @xmath95 , @xmath419    we will apply this proposition to prove theorem  [ lsupth ] . in what follows in the proof , denote @xmath420 . in our case , @xmath421 , @xmath22 plays the role of @xmath413 , and @xmath422 plays the role of @xmath20 . let @xmath423 , @xmath424 and @xmath425 . first , we need to upper bound the rademacher complexity @xmath426 for the class @xmath409 . let @xmath427 be the set of all symmetric @xmath15 matrices @xmath34 with @xmath172 and @xmath428 . the @xmath285-covering number @xmath429 of the set @xmath427 with respect to the hilbert schmidt distance ( i.e. , the minimal number of balls of radius @xmath285 needed to cover this set ) can be bounded as follows : @xmath430 such bounds are well known ( see , e.g. ,  @xcite , lemma 9.3 and references therein ; the proof of this lemma can be easily modified to obtain ( [ cover2 ] ) ) . bound ( [ cover2 ] ) will be used to control the covering numbers of the set of kernels @xmath431 . this set can be easily identified with a subset of the set @xmath432 [ since kernels @xmath433 can be viewed as symmetric @xmath147 matrices of rank at most @xmath434 with @xmath435 and @xmath436 . therefore , we get the following bound : @xmath437 since @xmath438 ( truncation of the entries reduces the hilbert  schmidt distance ) , we also have @xmath439 since @xmath440 , @xmath441 therefore , we get the following bound on the @xmath442-covering numbers of the set @xmath443 here @xmath444 denotes the empirical distribution based on observations @xmath445 . the last bound allows us to use inequality ( 3.17 ) in  @xcite to control the localized rademacher complexity @xmath426 of the class @xmath409 as follows : @xmath446 \\[-8pt ] \nonumber & \leq & c_1 \biggl[\sqrt{\frac{\delta l(r\wedge l)}{n}}\sqrt{\log \biggl ( \frac{am}{\sqrt{\delta } } \biggr ) } \vee\frac{l(r\wedge l)}{n}\log \biggl(\frac{am}{\sqrt{\delta } } \biggr ) \biggr]\end{aligned}\ ] ] with some constant @xmath447 . this easily yields @xmath448 with some constants @xmath449 . proposition  [ regr ] now implies bound ( [ lsoracul ] ) . to prove bound ( [ lsup ] ) , it is enough to observe that , for @xmath175 , @xmath450 indeed , since @xmath175 , we can approximate this kernel by @xmath451 for the error of this approximation , we have @xmath452 & & \quad= m^{-2 } \|s_l - s_{\ast}\|_2 ^ 2= m^{-2}\sum_{i\vee j > l } \langle s_{\ast } \phi_i,\phi_j\rangle^2 \\[-2pt ] & & \quad\leq m^{-2}\frac{1}{\lambda_{l+1 } } \sum_{i > l}\sum _ { j=1}^m \lambda _ i\langle s_{\ast}\phi_i,\phi_j\rangle^2 + m^{-2}\frac{1}{\lambda_{l+1 } } \sum_{i=1}^m \sum_{j > l } \lambda _ j\langle s_{\ast}\phi_i,\phi_j\rangle^2\leq \frac{2\rho ^2}{\lambda_{l+1}},\end{aligned}\ ] ] which implies @xmath453 ( since the entries of matrix @xmath10 are bounded by @xmath75 and truncation of the entries reduces the hilbert schmidt distance ) . we also have @xmath454 and @xmath455 therefore , @xmath456 and bound ( [ appro ] ) follows . bound ( [ lsup ] ) is a consequence of  ( [ lsoracul ] ) and ( [ appro ] ) .    note that , in the case when the basis of eigenfunctions @xmath148 coincides with the canonical basis of space @xmath64 , the following bound holds trivially : @xmath457 this follows from the fact that the entries of both matrices @xmath458 and @xmath459 are bounded by @xmath163 , and their nonzero entries are only in the first @xmath460 rows and the first @xmath460 columns , so , @xmath461 combining this with ( [ lsup ] ) and minimizing the resulting bound with respect to @xmath460 yields the following upper bound ( up to a constant ) that holds for the optimal choice of @xmath460 : @xmath462\vee\frac{a^2 t}{n}.\ ] ] it is not hard to check that , typically , this expression is of the same order ( up to log factors ) as the lower bound of theorem  [ lowerboundsparse ] for @xmath191 . next we consider a penalized version of least squares estimator which is adaptive to unknown parameters of the problem ( such as the rank of the target matrix and the optimal value of parameter @xmath460 which minimizes the error bound of theorem  [ lsupth ] ) . we still assume that @xmath25 a.s . for some known constant @xmath24 . define @xmath463 \\[-8pt ] \nonumber & & \hspace*{45pt}{}+k\frac{a^2 ( r\wedge l)l}{n}\log \biggl(\frac{a n m}{(r\wedge l)l } \biggr ) \biggr\}\end{aligned}\ ] ] and let @xmath464 . here @xmath465 and @xmath466 are fixed constants . the following theorem provides an oracle inequality for the estimator @xmath92 . [ regradapt ] there exists a choice of constants @xmath465 , @xmath466 in ( [ penls ] ) and @xmath87 in the inequality below such that for all @xmath93 with probability at least @xmath95 @xmath467.\nonumber\end{aligned}\ ] ]    as in the proof of the previous theorem , we can assume that @xmath402 the general case follows by rescaling . we will use oracle inequalities in abstract penalized empirical risk minimization problems ; see  @xcite , theorem  6.5 . we only sketch the proof here skipping the details that are standard . as in the proof of theorem  [ lsupth ] , first consider i.i.d . copies @xmath404 of a random couple @xmath405 in @xmath406 , where @xmath407 is a measurable space and @xmath408 a.s . let @xmath468 be a finite family of classes of measurable functions from @xmath410 into @xmath469 $ ] . consider the corresponding family of least squares estimators @xmath470 suppose the following upper bounds on localized rademacher complexities for classes @xmath471 hold : @xmath472 where @xmath473 are nondecreasing functions of @xmath474 that do not depend on the distribution of @xmath405 . let @xmath475,\ ] ] and @xmath476 are constants and @xmath477 are positive numbers . define the following penalized least squares estimator of the regression function . the next result is well known ; it can be deduced , for instance , from theorem  6.5 in  @xcite . [ regror ] there exists constants @xmath478 in the definition ( [ regpe ] ) of @xmath479 and a constant @xmath480 such that , for all @xmath481 , with probability at least @xmath482 @xmath483.\ ] ]    we apply this result to the estimator @xmath484 , where @xmath485 is defined by ( [ penls ] ) ( with @xmath486 ) . in this case , @xmath421 , @xmath22 plays the role of @xmath413 , @xmath487 , @xmath488 , @xmath489 . in view of ( [ radem ] ) , we can use the following bounds on localized rademacher complexities for these function classes : @xmath490\ ] ] with some constant @xmath491 , and we have @xmath492 with some constant @xmath493 . define @xmath494 . this yields the bound @xmath495 these considerations and proposition  [ regror ] imply the claim of the theorem . it follows from theorem  [ regradapt ] that , for some constant @xmath87 and for all @xmath93 , @xmath496 where @xmath497 . $ ] denoting @xmath498 it is easy to see that @xmath499    suppose that , for some @xmath158 , @xmath213 . under this assumption , it is easy to show that the upper bound on the squared @xmath58-error of the estimator @xmath92 is of the order @xmath500 ( in fact , the log factors can be written in a slightly better , but more complicated way ) . up to the log factors , this is the same error rate as in the lower bounds of section  [ sectlowerbound ] ; see ( [ minmaxlower ] ) . our main goal in this section is to study the following penalized least squares estimator with a combination of two convex penalties : @xmath501,\hspace*{-35pt}\ ] ] where @xmath502 is a closed convex set of symmetric kernels such that , for all @xmath503 , @xmath504 and @xmath505 are regularization parameters . the first penalty involved in ( [ lsnucsob ] ) is based on the nuclear norm @xmath506 , and it is used to `` promote '' low - rank solutions . the second penalty is based on a `` sobolev type norm '' @xmath507 . it is used to `` promote '' the smoothness of the solution on the graph . we will derive an upper bound on the error @xmath508 of estimator @xmath509 in terms of spectral characteristics of the target kernel @xmath10 and matrix  @xmath132 . as before , @xmath132 is a nonnegatively definite symmetric kernel with spectral representation @xmath133 where @xmath134 are the eigenvalues of @xmath132 repeated with their multiplicities and @xmath135 are the corresponding orthonormal eigenfunctions . we will also use the decomposition of identity associated with @xmath132 : @xmath510 clearly , @xmath511 is a nondecreasing projector - valued function . despite the fact that the eigenfunctions @xmath512 are not uniquely defined in the case when @xmath132 has multiple eigenvalues , the decomposition of identity @xmath513 is uniquely defined ( in fact , it can be rewritten in terms of spectral projectors of @xmath132 ) . the distribution of the eigenvalues of @xmath132 is characterized by the following _ spectral function _ : @xmath514 denote @xmath515 ( in other words , @xmath516 is the smallest @xmath517 such that @xmath518 ) . it was assumed in the that there exists a constant @xmath519 such that @xmath520 for all @xmath140 .    in what follows , we use a regularized majorant of spectral function @xmath521 . let @xmath522 be a nondecreasing function such that @xmath523 , the function @xmath524 is nonincreasing and , for some @xmath525 , @xmath526 without loss of generality , we assume in what follows that @xmath527 [ otherwise , one can take the function @xmath528 instead ] . the conditions on @xmath529 are satisfied if for some @xmath525 , the function @xmath530 is nonincreasing : in this case , @xmath531 is also nonincreasing and @xmath532    consider a kernel @xmath130 ( an oracle ) with spectral representation : @xmath533 , where @xmath534 , @xmath535 are nonzero eigenvalues of @xmath34 ( possibly repeated ) and @xmath536 are the corresponding orthonormal eigenfunctions . denote @xmath537 . the following _ coherence function _ will be used to characterize the relationship between the kernels @xmath34 and  @xmath132 : @xmath538 it is immediate from this definition that @xmath539 note also that @xmath540 is a nondecreasing function of @xmath541 and @xmath542 [ for @xmath543 , @xmath540 can be interpreted as a `` partial rank '' of @xmath34 ] . as in the case of spectral function @xmath34 , we need a regularized majorant for the coherence function @xmath540 . denote by @xmath545 the set of all nondecreasing functions @xmath546 such that @xmath547 is nonincreasing and @xmath548 . it is easy to see that the class of functions @xmath549 contains the smallest function ( uniformly in @xmath550 ) that will be denoted by @xmath551 and it is given by the following expression : @xmath552 it easily follows from this definition that @xmath553 . note that since the function @xmath554 is nonincreasing and it is equal to @xmath555 for @xmath556 , we have @xmath557      [ main ] there exists constants @xmath562 depending only on @xmath563 such that , for all @xmath564 $ ] with probability at least @xmath95 , @xmath565 \\ & & \qquad\quad{}+ c\frac{a^2 t_{n , m}}{n}.\nonumber\end{aligned}\ ] ]      \(2 ) note also that theorem  [ main ] holds in the case when @xmath569 . in this case , our method coincides with nuclear norm penalized least squares ( matrix lasso ) and @xmath570 , so the bound of theorem  [ main ] becomes @xmath571 + c\frac{a^2 t_{n , m}}{n}.\hspace*{-35pt}\ ] ] similar oracle inequalities were proved in  @xcite for a linearized least squares method with nuclear norm penalty . using simple aggregation techniques , it is easy to construct an adaptive estimator for which the oracle inequality of theorem  [ main ] holds with the optimal value of @xmath572 that minimizes the right - hand side of the bound . to this end , divide the sample @xmath573 into two parts , @xmath574 where @xmath575 + 1 $ ] . the first part of the sample will be used to compute the estimators @xmath576 , @xmath577 , @xmath578 [ they are defined by ( [ lsnucsob ] ) , but they are based only on the first @xmath579 observations ] . the second part of the sample is used for model selection @xmath580 finally , let @xmath581 . [ mainadapt ] under the assumptions and notation of theorem  [ main ] , with probability at least @xmath95 , @xmath582 } \bigl(m^2 \eps^2 \bar\varphi\bigl(s;\bar \eps^{-1}\bigr ) + \bar\eps\bigl\|w^{1/2}s\bigr\|_{l_2(\pi^2)}^2 \bigr ) \bigr ] \\ & & { } + c\frac{a^2 ( \log(m+1)+t_{n , m})}{n}.\nonumber\end{aligned}\ ] ]    the idea of aggregation result behind this theorem is rather well known ; see  @xcite , chapter 8 . the proof can be deduced , for instance , from proposition  [ regr ] used in section  [ sectlsnonconvex ] . specifically , this proposition has to be applied in the case when @xmath409 is a finite class of functions bounded by @xmath75 . let @xmath583 . then , for some numerical constant @xmath584 @xmath585\ ] ] ( see , e.g. ,  @xcite , theorem 3.5 ) , and proposition  [ regr ] easily implies that , for all @xmath93 , with probability at least @xmath95 @xmath586 where @xmath493 is a constant . we will assume that @xmath486 ( in the general case , the result would follow by rescaling ) and use bound ( [ finiteaggregate ] ) , conditionally on the first part of the sample , in the case when @xmath587 . then , given @xmath588 , with probability at least @xmath95 , @xmath589 by theorem  [ main ] [ with @xmath590 replaced by @xmath591 and the union bound , we get that , with probability at least @xmath95 , for all @xmath578 , @xmath592\\ & & \qquad\quad { } + c_3\frac{\log(m+1)+t_{n , m}}{n}\nonumber\end{aligned}\ ] ] with some constant @xmath593 . therefore , the minimal error of estimators @xmath458 , @xmath594 , can be bounded with the same probability by the minimum over @xmath595 of the expression in the right - hand side of ( [ boundthmain ] ) . moreover , using monotonicity of the function @xmath596 and the condition that @xmath597 , it is easy to replace the minimum over @xmath460 by the infimum over @xmath572 . combining the resulting bound with ( [ qua - qua ] ) and adjusting the constants yields the claim .    using more sophisticated aggregation methods ( e.g. , such as the methods studied in  @xcite ) it is possible to construct an estimator @xmath92 for which the oracle inequality similar to ( [ boundthmainadapt ] ) holds with constant @xmath75 in front of the approximation error term @xmath598 .    to understand better the meaning of function @xmath599 involved in the statements of theorems  [ main ] and  [ mainadapt ] , it makes sense to relate it to the low coherence assumptions discussed in the . indeed , suppose that , for some @xmath600 , @xmath601 this is a part of standard low coherence assumptions on matrix @xmath34 with respect to the orthonormal basis @xmath602 ; see ( [ cohera ] ) . clearly , it implies that ) with ( [ lowvarphi ] ) . ] @xmath603 suppose that @xmath604 and @xmath605 if condition ( [ up_varphi ] ) holds for the target kernel @xmath10 with @xmath82 and some @xmath83 , then theorem  [ main ] implies that with probability at least @xmath95 , @xmath606 and theorem  [ mainadapt ] implies that with the same probability , @xmath607 } \biggl(\frac{a^2\nu r \bar f(\bar\eps^{-1 } ) \log(2m)}{n } + \bar\eps \bigl\|w^{1/2}s_{\ast}\bigr\|_{l_2(\pi^2)}^2 \biggr)\\ & & { } + c \frac{a^2(\log(m+1)+ t_{n , m})}{n}.\end{aligned}\ ] ]    if @xmath608 for some @xmath609 , then it is easy to check that @xmath610 . under the assumption that @xmath611 , we get the bound @xmath612 under the following slightly modified version of low coherence assumption  ( [ up_varphi ] ) , @xmath613 one can almost recover upper bounds of section  [ sectlsnonconvex ] , @xmath614 the main difference with what was proved in section [ sectlsnonconvex ] is that now the low coherence constant @xmath85 is involved in the bounds , so the methods discussed in this section yield correct ( up to log factors ) error rates provided that the target kernel @xmath10 has `` low coherence '' with respect to the basis of eigenfunctions of @xmath132 . proof of theorem  [ main ] bound ( [ bound_th_main ] ) will be proved for a fixed oracle @xmath503 and an arbitrary function @xmath615 with @xmath616 instead of @xmath617 . it then can be applied to the function @xmath599 ( which is the smallest function in @xmath549 ) . without loss of generality , we assume that @xmath486 ; the general case then follows by a simple rescaling . finally , we will denote @xmath618 throughout the proof . define the following orthogonal projectors @xmath619 in the space @xmath68 with hilbert schmidt inner product : @xmath620 we will use a well known representation of subdifferential of convex function @xmath621 : @xmath622 where @xmath623 ; see  @xcite , appendix a.4 and references therein . denote @xmath624 so that @xmath625 . an arbitrary matrix @xmath626 can be represented as @xmath627 where @xmath628 . since @xmath629 is a minimizer of @xmath630 , there exists a matrix @xmath631 such that @xmath632 belongs to the normal cone of @xmath633 at the point @xmath629 ; see  @xcite , chapter 2 , corollary 6 . this implies that @xmath634 and , in view of ( [ aravno ] ) , @xmath635 \\[-8pt ] \nonumber & & \qquad{}+ 2\frac{\bar\eps}{m^2 } \langle w\hat{s},\hat{s}-s \rangle\leq0.\end{aligned}\ ] ] here and in what follows @xmath636 denotes the empirical distribution based on the sample @xmath637 . the corresponding true distribution of @xmath18 will be denoted by @xmath638 . it easily follows from ( [ aravno1 ] ) that @xmath639 where @xmath640 we can now rewrite the last bound as @xmath641 and use a simple identity @xmath642 to get the following bound : @xmath643    for an arbitrary @xmath644 , @xmath645 , where @xmath646 is a matrix with @xmath647 . it follows from the trace duality property that there exists an @xmath646 with @xmath648 [ to be specific , @xmath649 such that @xmath650 where the first equality is based on the fact that @xmath651 is a self - adjoint operator and the second equality is based on the fact that @xmath34 has support @xmath79 . using this equation and monotonicity of subdifferentials of convex functions , we get @xmath652 substituting this into the left - hand side of ( [ eqstep1 ] ) , it is easy to get @xmath653 \\[-8pt ] \nonumber & & \qquad\quad{}-2\bar\eps\bigl\langle w^{1/2}s , w^{1/2}(\hat s - s)\bigr\rangle_{l_2(\pi^2 ) } \\ & & \qquad\quad { } + 2 \langle\xi,\hat s - s\rangle + 2(p - p_n ) ( s - s_{\ast } ) ( \hat s - s)\nonumber \\ & & \qquad\quad{}+2(p - p_n ) ( \hat s - s)^2.\nonumber\end{aligned}\ ] ]    we need to bound the right - hand side of ( [ basic ] ) . we start with deriving a bound on @xmath654 , expressed in terms of function @xmath655 . note that , for all @xmath656 , @xmath657 which easily implies @xmath658 \\[-8pt ] \nonumber & & \qquad\quad{}+ \biggl(\sum_{\lambda_k>\lambda } \frac{\|\operatorname { sign}(s)\phi_k\|^2}{\lambda_k } \biggr)^{1/2 } \biggl(\sum_{\lambda_k>\lambda } \lambda_k\bigl\|(\hat s - s)\phi_k\bigr\| ^2 \biggr)^{1/2 } \\ & & \qquad\leq \biggl(\sum_{\lambda_k\leq\lambda } \|p_l \phi_k\|^2 \biggr)^{1/2}\| \hat s - s \|_2 + \biggl(\sum_{\lambda_k>\lambda } \frac{\|p_l\phi_k\|^2}{\lambda_k } \biggr)^{1/2 } \bigl\|w^{1/2}(\hat s - s ) \bigr\|_2.\nonumber\hspace*{-35pt}\end{aligned}\ ] ]        denote @xmath661 . suppose that @xmath662 $ ] for some @xmath663 . we will use the properties of functions @xmath615 and @xmath529 . in particular , recall that the functions @xmath664 and @xmath531 are nonincreasing . using these properties and the condition that @xmath665 we get @xmath666 which proves the first bound . to prove the second bound , replace in the inequalities above @xmath667 by @xmath75 and @xmath668 by @xmath669 . in the case when @xmath556 , both bounds are trivial since their left - hand sides are equal to zero . it follows from from ( [ odin ] ) and the first bound of lemma [ boundsums ] that @xmath670 this implies the following bound : @xmath671 where we used twice an elementary inequality @xmath672 . we will apply this bound for @xmath673 to get the following inequality : @xmath674    to bound the next term in the right - hand side of ( [ basic ] ) , note that @xmath675 \\[-8pt ] \nonumber & & \qquad\leq \bar\eps\bigl\|w^{1/2}s \bigr\|_{l_2(\pi^2)}^2 + \frac{\bar\eps}{4}\bigl\| w^{1/2}(\hat s - s)\bigr\|_{l_2(\pi^2)}^2.\end{aligned}\ ] ]    the main part of the proof deals with bounding the stochastic term @xmath676 on the right - hand side of ( [ basic ] ) . to this end , define ( for fixed @xmath677 ) @xmath678 and consider the following empirical process : @xmath679 where @xmath680 clearly , we have @xmath681 \\[-8pt ] \nonumber & & \qquad\leq 2\alpha_n \bigl(\|\hat s - s\|_{l_2(\pi^2 ) } , \bigl\|{\cal p}_{l}^{\perp}\hat s\bigr\|_1,\bigl \|w^{1/2}(\hat s - s)\bigr\|_{l_2(\pi^2 ) } \bigr),\end{aligned}\ ] ] and it remains to provide an upper bound on @xmath682 that is uniform in some intervals of the parameters @xmath683 ( such that either the norms @xmath684 belong to these intervals with a high probability , or bound of the theorem trivially holds ) . note that the functions @xmath685 are uniformly bounded by a numerical constant ( under the assumptions that @xmath486 , @xmath25 and all the kernels are also bounded by @xmath163 ) and we have @xmath686 with some numerical constant @xmath687 . using talagrand s concentration inequality for empirical processes we conclude that for fixed @xmath688 with probability at least @xmath95 and with some constant @xmath689 we will make this bound uniform in @xmath690 , \delta_k^-<\delta_k^+ , k=1,2,3 $ ] ( these intervals will be chosen later ) . define @xmath691 + 1 , k=1,2,3 $ ] and let @xmath692 + 2 ) . $ ] by the union bound , with probability at least @xmath95 and for all @xmath693 + 1 , k=1,2,3 $ ] , @xmath694 by monotonicity of @xmath695 and of the right - hand side of the bound with respect to each of the variables @xmath696 , we conclude that with the same probability and with some numerical constant @xmath697 , for all @xmath698 , k=1,2,3 $ ] , @xmath699    to bound the expectation @xmath700 on the right - hand side of ( [ talagr ] ) , note that , by the definition of function @xmath701 , @xmath702 & & \qquad\quad{}+ { \mathbb e}\sup \bigl\ { \bigl|(p_n - p ) ( a - s)^2 \bigr| \dvtx a\in{\cal t}(\delta_1,\delta_2 , \delta_3 ) \bigr\}.\nonumber\end{aligned}\ ] ] a standard application of symmetrization inequality followed by contraction inequality for rademacher sums ( see , e.g. ,  @xcite , chapter 2 ) yields @xmath703 \\[-9pt ] \nonumber & & \qquad \leq 16 { \mathbb e}\sup \bigl\ { \bigl|r_n(a - s ) \bigr|\dvtx a\in{\cal t}(\delta_1,\delta_2 , \delta_3 ) \bigr\}.\end{aligned}\ ] ] it easily follows from ( [ expal1 ] ) and ( [ expal2 ] ) that @xmath704 \\[-9pt ] \nonumber & & { } + 16 { \mathbb e}\sup \bigl\{\bigl|\langle\xi_2 , a - s\rangle\bigr| \dvtx a\in{\cal t}(\delta_1,\delta_2 , \delta_3 ) \bigr\},\end{aligned}\ ] ] where @xmath705 and @xmath706 being i.i.d . rademacher random variables independent of @xmath637 . we will upper bound the expectations on the right - hand side of ( [ expal3 ] ) , which reduces to bounding @xmath707 for each of the random matrices @xmath708 . for @xmath709 and @xmath710 , we have @xmath711 & \leq&\bigl|\langle{\cal p}_l\xi_i , a - s\rangle\bigr|+ \|\xi_i\|\bigl\|{\cal p}_l^{\perp}(a ) \bigr\|_1\\[-2pt ] & \leq&\bigl|\langle{\cal p}_l \xi_i , a - s\rangle\bigr|+ \delta_2 \|\xi_i\|.\nonumber\end{aligned}\ ] ] to bound @xmath712 , we use the following simple corollary of a well - known noncommutative bernstein inequality ( see , e.g. , @xcite ) obtained by integrating exponential tails of this inequality : let @xmath713 be a random symmetric matrix with @xmath714 , @xmath715 and @xmath716 for some @xmath717 and let @xmath718 be @xmath5 i.i.d . copies of @xmath713 . then @xmath719 it is applied to i.i.d . random matrices @xmath720 in the case of matrix @xmath721 and to i.i.d . random matrices @xmath722 in the case of matrix @xmath723 . in both cases , @xmath724 and , by a simple computation , @xmath725 ( see , e.g. , @xcite , section 9.4 ) , bound ( [ opber ] ) implies that , for @xmath709 , @xmath726= : \eps^{\ast}.\ ] ]        for all symmetric @xmath15 matrices @xmath646 , @xmath730 assuming that @xmath731   \bigl\|w^{1/2}m\bigr\|_2 ^ 2 & = & \sum_{k , j=1}^m \lambda_k \bigl| \langle m , \phi_k\otimes\phi_j\rangle \bigr|^2 \leq1,\end{aligned}\ ] ] it is easy to conclude that @xmath732 it follows @xmath733 & & \qquad\leq \biggl(\sum_{k , j=1}^m \bigl ( \lambda_k^{-1}\wedge\delta^2\bigr)\bigl|\langle{\cal p}_l \xi , \phi_k \otimes\phi_j \rangle\bigr|^2 \biggr)^{1/2 } \biggl(\sum _ { k , j=1}^m \frac{|\langle m , \phi_k\otimes\phi_j\rangle|^2}{\lambda _ k^{-1}\wedge\delta^2 } \biggr)^{1/2 } \\ & & \qquad\leq \sqrt{2 } \biggl(\sum_{k , j=1}^m \bigl(\lambda_k^{-1}\wedge\delta^2\bigr)\bigl| \langle{\cal p}_l \xi , \phi_k \otimes\phi_j \rangle\bigr|^2 \biggr)^{1/2}.\nonumber\end{aligned}\ ] ] consider the following inner product : @xmath734 and let @xmath735 be the corresponding norm . we will provide an upper bound on @xmath736 recall that @xmath737 where @xmath738 for @xmath739 and @xmath740 for @xmath741 . note that in the first case @xmath742 , and in the second case @xmath743 . therefore , @xmath744 \\[-9pt ] \nonumber & \leq&2\sqrt{\frac{{\mathbb e}\|{\cal p}_l e_{x , x'}\|_w^2}{n}}.\end{aligned}\ ] ] it remains to bound @xmath745 , @xmath746 & & \qquad= { \mathbb e}\sum_{k , j=1}^m \bigl(\lambda_k^{-1}\wedge\delta^2\bigr)\bigl|\bigl \langle { \cal p}_l ( e_{x , x ' } ) , \phi_k \otimes \phi_j\bigr\rangle\bigr|^2 \nonumber\\[-2pt ] & & \qquad= \sum_{k , j=1}^m \bigl ( \lambda_k^{-1}\wedge\delta^2\bigr ) m^{-2}\sum_{u , v\in v}\bigl|\bigl\langle e_{u , v } , { \cal p}_l(\phi_k \otimes\phi _ j)\bigr\rangle\bigr|^2 \nonumber\\[-2pt ] & & \qquad\leq m^{-2}\sum_{k , j=1}^m \bigl(\lambda_k^{-1}\wedge\delta^2\bigr ) \bigl\| { \cal p}_l(\phi_k \otimes\phi_j ) \bigr\|_2 ^ 2 \\[-2pt ] & & \qquad\leq 2m^{-2}\sum_{k , j=1}^m \bigl(\lambda_k^{-1}\wedge\delta^2\bigr ) \bigl(\|p_l\phi_k\|^2+\|p_l \phi_j\|^2\bigr ) \nonumber\\[-2pt ] & & \qquad= 2m^{-1}\sum_{k=1}^m \bigl(\lambda_k^{-1}\wedge\delta^2\bigr ) \|p_l\phi_k\|^2 + 2m^{-2}\sum _ { k=1}^m \bigl(\lambda_k^{-1 } \wedge\delta^2\bigr)\|p_l\|_2 ^ 2 \nonumber\\[-2pt ] & & \qquad= 2m^{-1}\sum_{k=1}^m \bigl(\lambda_k^{-1}\wedge\delta^2\bigr ) \|p_l\phi_k\|^2 + 2m^{-2}r\sum _ { k=1}^m \bigl(\lambda_k^{-1 } \wedge\delta^2\bigr).\nonumber\end{aligned}\ ] ] note that @xmath747    using the first bound of lemma  [ boundsums ] , we get from ( [ hi - hi ] ) that @xmath748 \\[-8pt ] \nonumber & = & ( c_{\gamma}+1 ) \delta^2 \varphi\bigl(\delta^{-2}\bigr).\end{aligned}\ ] ] we also have @xmath749 which , by the second bound of lemma  [ boundsums ] , implies that @xmath750 using bounds ( [ var ] ) , ( [ au ] ) and ( [ ua ] ) and the fact that @xmath751 , we get @xmath752 \\[-8pt ] \nonumber & \leq & 4m^{-1}(c_{\gamma}+1 ) \delta^2\varphi\bigl(\delta^{-2}\bigr).\end{aligned}\ ] ]      let @xmath753 . using lemma  [ lemma1 ] , we get @xmath754 in the case when @xmath755 , we get @xmath756 in the opposite case , when @xmath757 , we use the fact that the function @xmath758 is nonincreasing . this implies that @xmath759 , and we get @xmath760 we can conclude that @xmath761 this bound will be combined with ( [ pjat ] ) and ( [ expectxi ] ) to get that , for @xmath709 , @xmath762 in view of ( [ expal3 ] ) , this yields the bound @xmath763 that holds with some constant @xmath764 for all @xmath765 . using ( [ talagr ] ) , we conclude that for some constants @xmath766 and for all @xmath698 , k=1,2,3 $ ] , @xmath767\ ] ] that holds with probability at least @xmath95 . this yields the following upper bound on the stochastic term in ( [ basic ] ) [ see also ( [ stochterm ] ) ] : @xmath768\nonumber\end{aligned}\ ] ] that holds provided that @xmath769,\qquad \bigl\|{\cal p}_l^{\perp } \hat s \bigr\|_1\in\bigl[\delta_2 ^ -,\delta_2^+\bigr ] , \nonumber \\[-8pt ] \\[-8pt ] \nonumber \bigl\|w^{1/2}(\hat s - s)\bigr\|_{l_2(\pi^2)}&\in&\bigl[\delta_3 ^ - , \delta_3^+\bigr].\end{aligned}\ ] ] we substitute bound ( [ stochtermbound ] ) in ( [ basic ] ) and further bound some of its terms as follows : @xmath770 and @xmath771 we will also use ( [ tri  ] ) to control the term @xmath772 in ( [ basic ] ) and ( [ chetyre ] ) to control the term @xmath773 . if condition ( [ condeps ] ) holds with @xmath774 , then @xmath775 . by a simple algebra , it follows from ( [ basic ] ) that @xmath776 with some constant @xmath584 . since , under condition ( [ condeps ] ) with @xmath486 , @xmath777 , we can conclude that @xmath778 \\[-8pt ] \nonumber & & \qquad\leq \|s - s_{\ast}\|_{l_2(\pi^2)}^2 + c_2 m^2 \eps^2\varphi\bigl(\bar\eps^{-1}\bigr ) + \bar\eps\bigl\|w^{1/2}s\bigr\|_{l_2(\pi^2)}^2 + \frac{\bar t}{n}\end{aligned}\ ] ] with some constant @xmath493 . we still have to choose the values of @xmath779 and to handle the case when conditions ( [ conddel ] ) do not hold . first note that due to the assumption that @xmath780 , we have @xmath781 , @xmath782 and @xmath783 thus , we can set @xmath784 , which guarantees that the upper bounds of ( [ conddel ] ) are satisfied . we will also set @xmath785 in the case when one of the lower bounds of ( [ conddel ] ) does not hold , we can still use inequality ( [ stochtermbound ] ) , but we have to replace each of the norms @xmath786 which are smaller than the corresponding @xmath787 by the quantity @xmath787 . then it is straightforward to check that inequality ( [ finis ] ) still holds for some value of constant @xmath493 . with the above choice of @xmath788 , we have @xmath789 this completes the proof .
let @xmath0 be a weighted graph with a finite vertex set @xmath1 , with a symmetric matrix of nonnegative weights @xmath2 and with laplacian @xmath3 . 
 let @xmath4 be a symmetric kernel defined on the vertex set @xmath1 . 
 consider @xmath5 i.i.d . 
 observations @xmath6 , where @xmath7 are independent random vertices sampled from the uniform distribution in @xmath1 and @xmath8 is a real valued response variable such that @xmath9 . 
 the goal is to estimate the kernel @xmath10 based on the data @xmath11 and under the assumption that @xmath10 is low rank and , at the same time , smooth on the graph ( the smoothness being characterized by discrete sobolev norms defined in terms of the graph laplacian ) . 
 we obtain several results for such problems including minimax lower bounds on the @xmath12-error and upper bounds for penalized least squares estimators both with nonconvex and with convex penalties .