We consider the general question of estimating decay of correlations for non-uniformly expanding maps, for classes of observables which are much larger than the usual class of Holder continuous functions. Our results give new estimates for many non-uniformly expanding systems, including Manneville-Pomeau maps, many one-dimensional systems with critical points, and Viana maps. In many situations, we also obtain a Central Limit Theorem for a much larger class of observables than usual. Our main tool is an extension of the coupling method introduced by L.-S. Young for estimating rates of mixing on certain non-uniformly expanding tower maps.
The have been various results concerned primarily with weakening the assumption on the regularity of @math , and obtaining (slower) upper bounds for the rate of mixing with respect to the corresponding equilibrium measures. Kondah, Maume and Schmitt ( @cite_15 ) used a method of Birkhoff cones and projective metrics, Bressaud, Fernandez and Galves ( @cite_4 ) used a coupling method (different from the one described here), with estimates given in terms of , and Pollicott ( @cite_14 ) introduced a method involving composing transfer operators with conditional expectations. Each of these results has slightly different assumptions and gives slightly different estimates, but in each case a number of different classes of potentials are considered, and estimates are given for for observables of some similar regularity to (usually than) the potential. In particular, in all three examples polynomial mixing is given for a potential and observables with variations decaying at suitable polynomial rates.
@cite_15 @cite_14 @cite_4
2169660011 1555319984 2140237849
We present an upper bound on the mixing rate of the equilibrium state of a dynamical system defined by the one-sided shift and a non Holder potential of summable variations. The bound follows from an estimation of the relaxation speed of chains with complete connections with summable decay, which is obtained via a explicit coupling between pairs of chains with different histories. This paper has two parts. In the first part we consider a simple Markov chain for d-regular graphs on n vertices, where d = d(n) may grow with n. We show that the mixing time of this Markov chain is bounded above by a polynomial in n and d. In the second part of the paper, a related Markov chain for d-regular graphs on a varying number of vertices is introduced, for even constant d. This is a model for a certain peer-to-peer network. We prove that the related chain has mixing time which is bounded above by a polynomial in N, the expected number of vertices, provided certain assumptions are met about the rate of arrival and departure of vertices. Motivated by the numerical treatment of parametric and stochastic PDEs, we analyze the least-squares method for polynomial approximation of multivariate functions based on random sampling according to a given probability measure. Recent work has shown that in the univariate case, the least-squares method is quasi-optimal in expectation in [A. Cohen, M A. Davenport and D. Leviatan. Found. Comput. Math. 13 (2013) 819–834] and in probability in [G. Migliorati, F. Nobile, E. von Schwerin, R. Tempone, Found. Comput. Math. 14 (2014) 419–456], under suitable conditions that relate the number of samples with respect to the dimension of the polynomial space. Here “quasi-optimal” means that the accuracy of the least-squares approximation is comparable with that of the best approximation in the given polynomial space. In this paper, we discuss the quasi-optimality of the polynomial least-squares method in arbitrary dimension. Our analysis applies to any arbitrary multivariate polynomial space (including tensor product, total degree or hyperbolic crosses), under the minimal requirement that its associated index set is downward closed. The optimality criterion only involves the relation between the number of samples and the dimension of the polynomial space, independently of the anisotropic shape and of the number of variables. We extend our results to the approximation of Hilbert space-valued functions in order to apply them to the approximation of parametric and stochastic elliptic PDEs. As a particular case, we discuss “inclusion type” elliptic PDE models, and derive an exponential convergence estimate for the least-squares method. Numerical results confirm our estimate, yet pointing out a gap between the condition necessary to achieve optimality in the theory, and the condition that in practice yields the optimal convergence rate. On complete, non-compact manifolds and infinite graphs, Faber-Krahn inequalities have been used to estimate the rate of decay of the heat kernel. We develop this technique in the setting of finite Markov chains, proving upper and lower @math mixing time bounds via the spectral profile. This approach lets us recover and refine previous conductance-based bounds of mixing time (including the Morris-Peres result), and in general leads to sharper estimates of convergence rates. We apply this method to several models including groups with moderate growth, the fractal-like Viscek graphs, and the product group @math , to obtain tight bounds on the corresponding mixing times. We study the density estimation problem with observations generated by certain dynamical systems that admit a unique underlying invariant Lebesgue density. Observations drawn from dynamical systems are not independent and moreover, usual mixing concepts may not be appropriate for measuring the dependence among these observations. By employing the @math -mixing concept to measure the dependence, we conduct statistical analysis on the consistency and convergence of the kernel density estimator. Our main results are as follows: First, we show that with properly chosen bandwidth, the kernel density estimator is universally consistent under @math -norm; Second, we establish convergence rates for the estimator with respect to several classes of dynamical systems under @math -norm. In the analysis, the density function @math is only assumed to be H " o lder continuous which is a weak assumption in the literature of nonparametric density estimation and also more realistic in the dynamical system context. Last but not least, we prove that the same convergence rates of the estimator under @math -norm and @math -norm can be achieved when the density function is H " o lder continuous, compactly supported and bounded. The bandwidth selection problem of the kernel density estimator for dynamical system is also discussed in our study via numerical simulations. We introduce the framework of blind regression motivated by matrix completion for recommendation systems: given @math users, @math movies, and a subset of user-movie ratings, the goal is to predict the unobserved user-movie ratings given the data, i.e., to complete the partially observed matrix. Following the framework of non-parametric statistics, we posit that user @math and movie @math have features @math and @math respectively, and their corresponding rating @math is a noisy measurement of @math for some unknown function @math . In contrast with classical regression, the features @math are not observed, making it challenging to apply standard regression methods to predict the unobserved ratings. Inspired by the classical Taylor's expansion for differentiable functions, we provide a prediction algorithm that is consistent for all Lipschitz functions. In fact, the analysis through our framework naturally leads to a variant of collaborative filtering, shedding insight into the widespread success of collaborative filtering in practice. Assuming each entry is sampled independently with probability at least @math with @math , we prove that the expected fraction of our estimates with error greater than @math is less than @math plus a polynomially decaying term, where @math is the variance of the additive entry-wise noise term. Experiments with the MovieLens and Netflix datasets suggest that our algorithm provides principled improvements over basic collaborative filtering and is competitive with matrix factorization methods. We consider the problem of one-step-ahead prediction of a real-valued, stationary, strongly mixing random process (Xi) sub i=- spl infin sup spl infin . The best mean-square predictor of X sub 0 is its conditional mean given the entire infinite past (X sub i ) sub i=- spl infin sup -1 . Given a sequence of observations X sub 1 , X sub 2 , X sub N , we propose estimators for the conditional mean based on sequences of parametric models of increasing memory and of increasing dimension, for example, neural networks and Legendre polynomials. The proposed estimators select both the model memory and the model dimension, in a data-driven fashion, by minimizing certain complexity regularized least squares criteria. When the underlying predictor function has a finite memory, we establish that the proposed estimators are memory-universal: the proposed estimators, which do not know the true memory, deliver the same statistical performance (rates of integrated mean-squared error) as that delivered by estimators that know the true memory. Furthermore, when the underlying predictor function does not have a finite memory, we establish that the estimator based on Legendre polynomials is consistent. We prove sharp pointwise t−3 decay for scalar linear perturbations of a Schwarzschild black hole without symmetry assumptions on the data. We also consider electromagnetic and gravitational perturbations for which we obtain decay rates t−4, and t−6, respectively. We proceed by decomposition into angular momentum l and summation of the decay estimates on the Regge-Wheeler equation for fixed l. We encounter a dichotomy: the decay law in time is entirely determined by the asymptotic behavior of the Regge-Wheeler potential in the far field, whereas the growth of the constants in l is dictated by the behavior of the Regge-Wheeler potential in a small neighborhood around its maximum. In other words, the tails are controlled by small energies, whereas the number of angular derivatives needed on the data is determined by energies close to the top of the Regge-Wheeler potential. This dichotomy corresponds to the well-known principle that for initial times the decay reflects the presence of complex resonances generated by the potential maximum, whereas for later times the tails are determined by the far field. However, we do not invoke complex resonances at all, but rely instead on semiclassical Sigal-Soffer type propagation estimates based on a Mourre bound near the top energy. Given data stream @math of size @math of numbers from @math , the frequency of @math is defined as @math . The @math -th of @math is defined as @math . We consider the problem of approximating frequency moments in insertion-only streams for @math . For any constant @math we show an @math upper bound on the space complexity of the problem. Here @math is the iterative @math function. To simplify the presentation, we make the following assumptions: @math and @math are polynomially far; approximation error @math and parameter @math are constants. We observe a natural bijection between streams and special matrices. Our main technical contribution is a non-uniform sampling method on matrices. We call our method a ; it samples a heavy element (i.e., element @math with frequency @math ) with probability @math and gives approximation @math . In addition, the estimations never exceed the real values, that is @math for all @math . As a result, we reduce the space complexity of finding a heavy element to @math bits. We apply our method of recursive sketches and resolve the problem with @math bits. Adapting and extending the techniques developed in recent work with Vasy for the study of the Cauchy horizon of cosmological spacetimes, we obtain boundedness, regularity and decay of linear scalar waves on subextremal Reissner-Nordstr "om and (slowly rotating) Kerr spacetimes, without any symmetry assumptions; in particular, we provide simple microlocal and scattering theoretic proofs of analogous results by Franzen. We show polynomial decay of linear waves relative to a Sobolev space of order slightly above @math . This complements the generic @math blow-up result of Luk and Oh. In this paper we consider a simple Markov chain for bipartite graphs with given degree sequence on @math vertices. We show that the mixing time of this Markov chain is bounded above by a polynomial in @math in case of half-regular degree sequence. The novelty of our approach lies in the construction of the multicommodity flow in Sinclair's method. In some statistical non-parametric models the mean of the random variable y has to satisfy specific constraints. We consider the case where the set defined by the constraints is a closed polyhedral cone K in Rk. For example, when the mean is required to be concave in x, the set of acceptable means is a closed convex cone defined by k-2 linear inequalities in Rk. The least squares estimate of the mean is then the projection of the data point y on the cone K. In this paper, we present an algorithm to find the least square estimate of the mean in a finite number of steps. Other algorithms to solve this problem have been given before. The successive approximations in such algorithms are usually points on the faces of K. The solution here is reached by following a fixed line joining an abitrary but suitably chosen initial point y0 to the data point y. The 1- dimensional subspace spanned by the generators of the cone K is divided into 2' regions which can be described as the set of points with non-negative coordinates in mixed primal-dual bases relative to the cone K. Any point y belongs to one and only one of these regions SJ with corresponding basis 3j. The projection of y on K is immediately obtained from the expression of y in Oj by dropping the dual component of y. Consider a set of @math agents seeking to solve distributively the minimization problem @math where the convex functions @math are local to the agents. The popular Alternating Direction Method of Multipliers has the potential to handle distributed optimization problems of this kind. We provide a general reformulation of the problem and obtain a class of distributed algorithms which encompass various network architectures. The rate of convergence of our method is considered. It is assumed that the infimum of the problem is reached at a point @math , the functions @math are twice differentiable at this point and @math in the positive definite ordering of symmetric matrices. With these assumptions, it is shown that the convergence to the consensus @math is linear and the exact rate is provided. Application examples where this rate can be optimized with respect to the ADMM free parameter @math are also given. We consider a family of open sets M? which shrinks with respect to an appropriate parameter ? to a graph. Under the additional assumption that the vertex neighbourhoods are small we show that the appropriately shifted Dirichlet spectrum of M? converges to the spectrum of the (differential) Laplacian on the graph with Dirichlet boundary conditions at the vertices, i.e., a graph operator without coupling between different edges. The smallness is expressed by a lower bound on the first eigenvalue of a mixed eigenvalue problem on the vertex neighbourhood. The lower bound is given by the first transversal mode of the edge neighbourhood. We also allow curved edges and show that all bounded eigenvalues converge to the spectrum of a Laplacian acting on the edge with an additional potential coming from the curvature. We consider the problem of estimating an unknown signal @math from noisy linear observations @math . In many practical instances, @math has a certain structure that can be captured by a structure inducing convex function @math . For example, @math norm can be used to encourage a sparse solution. To estimate @math with the aid of @math , we consider the well-known LASSO method and provide sharp characterization of its performance. We assume the entries of the measurement matrix @math and the noise vector @math have zero-mean normal distributions with variances @math and @math respectively. For the LASSO estimator @math , we attempt to calculate the Normalized Square Error (NSE) defined as @math as a function of the noise level @math , the number of observations @math and the structure of the signal. We show that, the structure of the signal @math and choice of the function @math enter the error formulae through the summary parameters @math and @math , which are defined as the Gaussian squared-distances to the subdifferential cone and to the @math -scaled subdifferential, respectively. The first LASSO estimator assumes a-priori knowledge of @math and is given by @math . We prove that its worst case NSE is achieved when @math and concentrates around @math . Secondly, we consider @math , for some @math . This time the NSE formula depends on the choice of @math and is given by @math . We then establish a mapping between this and the third estimator @math . Finally, for a number of important structured signal classes, we translate our abstract formulae to closed-form upper bounds on the NSE. A citing sentence is one that appears in a scientific article and cites previous work. Citing sentences have been studied and used in many applications. For example, they have been used in scientific paper summarization, automatic survey generation, paraphrase identification, and citation function classification. Citing sentences that cite multiple papers are common in scientific writing. This observation should be taken into consideration when using citing sentences in applications. For instance, when a citing sentence is used in a summary of a scientific paper, only the fragments of the sentence that are relevant to the summarized paper should be included in the summary. In this paper, we present and compare three different approaches for identifying the fragments of a citing sentence that are related to a given target reference. Our methods are: word classification, sequence labeling, and segment classification. Our experiments show that segment classification achieves the best results. Historically, papers have been physically bound to the journal in which they were published; but in the digital age papers are available individually, no longer tied to their respective journals. Hence, papers now can be read and cited based on their own merits, independently of the journal's physical availability, reputation, or impact factor (IF). We compare the strength of the relationship between journals' IFs and the actual citations received by their respective papers from 1902 to 2009. Throughout most of the 20th century, papers' citation rates were increasingly linked to their respective journals' IFs. However, since 1990, the advent of the digital age, the relation between IFs and paper citations has been weakening. This began first in physics, a field that was quick to make the transition into the electronic domain. Furthermore, since 1990 the overall proportion of highly cited papers coming from highly cited journals has been decreasing and, of these highly cited papers, the proportion not coming from highly cited journals has been increasing. Should this pattern continue, it might bring an end to the use of the IF as a way to evaluate the quality of journals, papers, and researchers. © 2012 Wiley Periodicals, Inc. We give the first dimension-efficient algorithms for learning Rectified Linear Units (ReLUs), which are functions of the form @math with @math . Our algorithm works in the challenging Reliable Agnostic learning model of Kalai, Kanade, and Mansour (2009) where the learner is given access to a distribution @math on labeled examples but the labeling may be arbitrary. We construct a hypothesis that simultaneously minimizes the false-positive rate and the loss on inputs given positive labels by @math , for any convex, bounded, and Lipschitz loss function. The algorithm runs in polynomial-time (in @math ) with respect to any distribution on @math (the unit sphere in @math dimensions) and for any error parameter @math (this yields a PTAS for a question raised by F. Bach on the complexity of maximizing ReLUs). These results are in contrast to known efficient algorithms for reliably learning linear threshold functions, where @math must be @math and strong assumptions are required on the marginal distribution. We can compose our results to obtain the first set of efficient algorithms for learning constant-depth networks of ReLUs. Our techniques combine kernel methods and polynomial approximations with a "dual-loss" approach to convex programming. As a byproduct we obtain a number of applications including the first set of efficient algorithms for "convex piecewise-linear fitting" and the first efficient algorithms for noisy polynomial reconstruction of low-weight polynomials on the unit sphere. We consider solutions to the linear wave equation @math on a non-extremal maximally extended Schwarzschild-de Sitter spacetime arising from arbitrary smooth initial data prescribed on an arbitrary Cauchy hypersurface. (In particular, no symmetry is assumed on initial data, and the support of the solutions may contain the sphere of bifurcation of the black white hole horizons and the cosmological horizons.) We prove that in the region bounded by a set of black white hole horizons and cosmological horizons, solutions @math converge pointwise to a constant faster than any given polynomial rate, where the decay is measured with respect to natural future-directed advanced and retarded time coordinates. We also give such uniform decay bounds for the energy associated to the Killing field as well as for the energy measured by local observers crossing the event horizon. The results in particular include decay rates along the horizons themselves. Finally, we discuss the relation of these results to previous heuristic analysis of Price and Iterative shrinkage thresholding (1ST) algorithms have been recently proposed to handle a class of convex unconstrained optimization problems arising in image restoration and other linear inverse problems. This class of problems results from combining a linear observation model with a nonquadratic regularizer (e.g., total variation or wavelet-based regularization). It happens that the convergence rate of these 1ST algorithms depends heavily on the linear observation operator, becoming very slow when this operator is ill-conditioned or ill-posed. In this paper, we introduce two-step 1ST (TwIST) algorithms, exhibiting much faster convergence rate than 1ST for ill-conditioned problems. For a vast class of nonquadratic convex regularizers (lscrP norms, some Besov norms, and total variation), we show that TwIST converges to a minimizer of the objective function, for a given range of values of its parameters. For noninvertible observation operators, we introduce a monotonic version of TwIST (MTwIST); although the convergence proof does not apply to this scenario, we give experimental evidence that MTwIST exhibits similar speed gains over IST. The effectiveness of the new methods are experimentally confirmed on problems of image deconvolution and of restoration with missing samples.