Orthogonal Matching Pursuit (OMP) is a canonical greedy pursuit algorithm for sparse approximation. Previous studies of OMP have considered the recovery of a sparse signal through Φ and y = Φx + b, where is a matrix with more columns than rows and denotes the measurement noise. In this paper, based on Restricted Isometry Property (RIP), the performance of OMP is analyzed under general perturbations, which means both y and Φ are perturbed. Though the exact recovery of an almost sparse signal x is no longer feasible, the main contribution reveals that the support set of the best k-term approximation of x can be recovered under reasonable conditions. The error bound between x and the estimation of OMP is also derived. By constructing an example it is also demonstrated that the sufficient conditions for support recovery of the best k-term approximation of are rather tight. When x is strong-decaying, it is proved that the sufficient conditions for support recovery of the best k-term approximation of x can be relaxed, and the support can even be recovered in the order of the entries' magnitude. Our results are also compared in detail with some related previous ones.
First, consider the ratio of the upper bounds on the recovery error in ) and ): @math According to Proposition 4.1 in @cite_25 , @math , and thus @math . This means that the error bound given by Corollary 1 @math is at least as good as that in [28, Th.5.1].
@cite_25
2950162031 2604884452 2000931246 2568310503
We investigate the clustering performances of the relaxed @math means in the setting of sub-Gaussian Mixture Model (sGMM) and Stochastic Block Model (SBM). After identifying the appropriate signal-to-noise ratio (SNR), we prove that the misclassification error decay exponentially fast with respect to this SNR. These partial recovery bounds for the relaxed @math means improve upon results currently known in the sGMM setting. In the SBM setting, applying the relaxed @math means SDP allows to handle general connection probabilities whereas other SDPs investigated in the literature are restricted to the assortative case (where within group probabilities are larger than between group probabilities). Again, this partial recovery bound complements the state-of-the-art results. All together, these results put forward the versatility of the relaxed @math means. We consider the problem of provably optimal exploration in reinforcement learning for finite horizon MDPs. We show that an optimistic modification to value iteration achieves a regret bound of @math where @math is the time horizon, @math the number of states, @math the number of actions and @math the number of time-steps. This result improves over the best previous known bound @math achieved by the UCRL2 algorithm of , 2010. The key significance of our new results is that when @math and @math , it leads to a regret of @math that matches the established lower bound of @math up to a logarithmic factor. Our analysis contains two key insights. We use careful application of concentration inequalities to the optimal value function as a whole, rather than to the transitions probabilities (to improve scaling in @math ), and we define Bernstein-based "exploration bonuses" that use the empirical variance of the estimated values at the next states (to improve scaling in @math ). Let f be a random Boolean formula that is an instance of 3-SAT. We consider the problem of computing the least real number k such that if the ratio of the number of clauses over the number of variables of f strictly exceeds k , then f is almost certainly unsatisfiable. By a well-known and more or less straightforward argument, it can be shown that kF5.191. This upper bound was improved by to 4.758 by first providing new improved bounds for the occupancy problem. There is strong experimental evidence that the value of k is around 4.2. In this work, we define, in terms of the random formula f, a decreasing sequence of random variables such that, if the expected value of any one of them converges to zero, then f is almost certainly unsatisfiable. By letting the expected value of the first term of the sequence converge to zero, we obtain, by simple and elementary computations, an upper bound for k equal to 4.667. From the expected value of the second term of the sequence, we get the value 4.601q . In general, by letting the U This work was performed while the first author was visiting the School of Computer Science, Carleton Ž University, and was partially supported by NSERC Natural Sciences and Engineering Research Council . of Canada , and by a grant from the University of Patras for sabbatical leaves. The second and third Ž authors were supported in part by grants from NSERC Natural Sciences and Engineering Research . Council of Canada . During the last stages of this research, the first and last authors were also partially Ž . supported by EU ESPRIT Long-Term Research Project ALCOM-IT Project No. 20244 . †An extended abstract of this paper was published in the Proceedings of the Fourth Annual European Ž Symposium on Algorithms, ESA’96, September 25]27, 1996, Barcelona, Spain Springer-Verlag, LNCS, . pp. 27]38 . That extended abstract was coauthored by the first three authors of the present paper. Correspondence to: L. M. Kirousis Q 1998 John Wiley & Sons, Inc. CCC 1042-9832r98r030253-17 253 The notion of recoverable value was advocated in the work of Feige, Immorlica, Mirrokni and Nazerzadeh (APPROX 2009) as a measure of quality for approximation algorithms. There, this concept was applied to facility location problems. In the current work we apply a similar framework to the maximum independent set problem (MIS). We say that an approximation algorithm has recoverable factor ρ, if for every graph it recovers an independent set of size at least where d(v) is the degree of vertex v, and I ranges over all independent sets in G. Hence, in a sense, from every vertex v in the maximum independent set the algorithm recovers a value of at least toward the solution. This quality measure is most effective in graphs in which the maximum independent set is composed of low degree vertices. A simple greedy algorithm achieves . We design a new randomized algorithm for MIS that ensures an expected recoverable factor of at least . In passing, we prove that approximating MIS in graphs with a given k-coloring within a ratio larger than 2 k is unique-games hard. This rules out an alternative approach for obtaining . © 2013 Wiley Periodicals, Inc. Random Struct. Alg., 46, 142–159, 2015