The best m-term approximation and greedy algorithms

Two theorems on nonlinear ‐term approximation in , are proved in this paper. The first one (theorem 2.1) says that if a basis is ‐equivalent to the Haar basis then a near best >‐term approximation to any can be realized by the following simple greedy type algorithm. Take the expansion and form a sum of terms with the largest out of this expansion. The second one (theorem 3.3) states that nonlinear ‐term approximations with regard to two dictionaries: the Haar basis and the set of all characteristic functions of intervals are equivalent in a very strong sense. This revised version was published online in June 2006 with corrections to the Cover Date.     

The rate of convergence of weak greedy approximations over orthogonal dictionaries

The convergence rate of a weak orthogonal greedy algorithm is studied for the subspace ?¹ ? ?² and orthogonal dictionaries. It is shown that general results on convergence rate of weak orthogonal greedy algorithms can be essentially improved in the studied case. It is also shown that this improvement is asymptotically sharp.     

Adaptive greedy approximations

The problem of optimally approximating a function with a linear expansion over a redundant dictionary of waveforms is NP-hard. The greedy matching pursuit algorithm and its orthogonalized variant produce suboptimal function expansions by iteratively choosing dictionary waveforms that best match the function’s structures. A matching pursuit provides a means of quickly computing compact, adaptive function approximations. Numerical experiments show that the approximation errors from matching pursuits initially decrease rapidly, but the asymptotic decay rate of the errors is slow. We explain this behavior by showing that matching pursuits are chaotic, ergodic maps. The statistical properties of the approximation errors of a pursuit can be obtained from the invariant measure of the pursuit. We characterize these measures using group symmetries of dictionaries and by constructing a stochastic differential equation model. We derive a notion of the coherence of a signal with respect to a dictionary from our characterization of the approximation errors of a pursuit. The dictionary elements slected during the initial iterations of a pursuit correspond to a function’s coherent structures. The tail of the expansion, on the other hand, corresponds to a noise which is characterized by the invariant measure of the pursuit map. When using a suitable dictionary, the expansion of a function into its coherent structures yields a compact approximation. We demonstrate a denoising algorithm based on coherent function expansions.     

Fast algorithms for greedy triangulation

We present the first quadratic-time algorithm for the greedy triangulation of a finite planar point set, and the first linear-time algorithm for the greedy triangulation of a convex polygon.     

Vector greedy algorithms

Our objective is to study nonlinear approximation with regard to redundant systems. Redundancy on the one hand offers much promise for greater efficiency in terms of approximation rate, but on the other hand gives rise to highly nontrivial theoretical and practical problems. Greedy-type approximations proved to be convenient and efficient ways of constructing m-term approximants. We introduce and study vector greedy algorithms that are designed with aim of constructing mth greedy approximants simultaneously for a given finite number of elements. We prove convergence theorems and obtain some estimates for the rate of convergence of vector greedy algorithms when elements come from certain classes.     

Realizability of greedy algorithms

We discuss new models of an “affine” theory of gravity in multidimensional space-times with symmetric connections. We use and develop ideas of Weyl, Eddington, and Einstein, in particular, Einstein’s proposal to specify the space-time geometry by the use of the Hamilton principle. More specifically, the connection coefficients are determined using a “geometric” Lagrangian that is an arbitrary function of the generalized (nonsymmetric) Ricci curvature tensor (and, possibly, of other fundamental tensors) expressed in terms of the connection coefficients regarded as independent variables. Such a theory supplements the standard Einstein gravity with dark energy (the cosmological constant, in the first approximation), a neutral massive (or tachyonic) vector field (vecton), and massive (or tachyonic) scalar fields. These fields couple only to gravity and can generate dark matter and/or inflation. The new field masses (real or imaginary) have a geometric origin and must appear in any concrete model. The concrete choice of the geometric Lagrangian determines further details of the theory, for example, the nature of the vector and scalar fields that can describe massive particles, tachyons, or even “phantoms.” In “natural” geometric theories, which are discussed here, dark energy must also arise. We mainly focus on intricate relations between geometry and dynamics while only very briefly considering approximate cosmological models inspired by the geometric approach.     

Super greedy type algorithms

We study greedy-type algorithms such that at a greedy step we pick several dictionary elements contrary to a single dictionary element in standard greedy algorithms. We call such greedy algorithms super greedy type algorithms. The super greedy type algorithms are computationally simpler than their analogues from the standard greedy algorithms. In this article, we propose the Weak Super Greedy Algorithm (WSGA) and the Weak Orthogonal Super Greedy Algorithm with Thresholding (WOSGAT). Their performance (rate of convergence) are studied as well under M-coherent dictionaries.     

On greedy algorithms for series parallel graphs

This note describes some sufficient conditions for the maximum or minimum of a weighted flow (the weights are on paths, and are derived from weights on the edges of the path), of given volume in a series parallel graph to be found by a greedy algorithm.     

GPU accelerated greedy algorithms for compressed sensing

For appropriate matrix ensembles, greedy algorithms have proven to be an efficient means of solving the combinatorial optimization problem associated with compressed sensing. This paper describes an implementation for graphics processing units (GPU) of hard thresholding, iterative hard thresholding, normalized iterative hard thresholding, hard thresholding pursuit, and a two-stage thresholding algorithm based on compressive sampling matching pursuit and subspace pursuit. The GPU acceleration of the former bottleneck, namely the matrix–vector multiplications, transfers a significant portion of the computational burden to the identification of the support set. The software solves high-dimensional problems in fractions of a second which permits large-scale testing at dimensions currently unavailable in the literature. The GPU implementations exhibit up to 70 $\times $ × acceleration over standard Matlab central processing unit implementations using automatic multi-threading.     

Phase transitions for greedy sparse approximation algorithms

A major enterprise in compressed sensing and sparse approximation is the design and analysis of computationally tractable algorithms for recovering sparse, exact or approximate, solutions of underdetermined linear systems of equations. Many such algorithms have now been proven to have optimal-order uniform recovery guarantees using the ubiquitous Restricted Isometry Property (RIP) (Candès and Tao (2005) [11]). However, without specifying a matrix, or class of matrices, it is unclear when the RIP-based sufficient conditions on the algorithm are satisfied. Bounds on RIP constants can be inserted into the algorithms RIP-based conditions, translating the conditions into requirements on the signal's sparsity level, length, and number of measurements. We illustrate this approach for Gaussian matrices on three of the state-of-the-art greedy algorithms: CoSaMP (Needell and Tropp (2009) [29]), Subspace Pursuit (SP) (Dai and Milenkovic (2009) [13]) and Iterative Hard Thresholding (IHT) (Blumensath and Davies (2009) [8]). Designed to allow a direct comparison of existing theory, our framework implies that, according to the best available analysis on these three algorithms, IHT requires the fewest number of compressed sensing measurements, has the best proven stability bounds, and has the lowest per iteration computational cost.     

Simultaneous approximation by greedy algorithms

We study nonlinear m-term approximation with regard to a redundant dictionary $\mathcal {D}$ in a Hilbert space H. It is known that the Pure Greedy Algorithm (or, more generally, the Weak Greedy Algorithm) provides for each f∈H and any dictionary $\mathcal {D}$ an expansion into a series $$f=\sum_{j=1}^{\infty}c_{j}(f)\varphi_{j}(f),\quad\varphi_{j}(f)\in \mathcal {D},\ j=1,2,\ldots,$$ with the Parseval property: ‖f‖²=∑_j|c _j(f)|². Following the paper of A. Lutoborski and the second author we study analogs of the above expansions for a given finite number of functions f ¹,.?.?.,f ^N with a requirement that the dictionary elements φ_j of these expansions are the same for all f ⁱ, i=1,.?.?.,N. We study convergence and rate of convergence of such expansions which we call simultaneous expansions.     

Some remarks on greedy algorithms

Estimates are given for the rate of approximation of a function by means of greedy algorithms. The estimates apply to approximation from an arbitrary dictionary of functions. Three greedy algorithms are discussed: the Pure Greedy Algorithm, an Orthogonal Greedy Algorithm, and a Relaxed Greedy Algorithm.This research was supported by the Office of Naval Research Contract N0014-91-J1343.     

Worst-case analysis of greedy algorithms for the subset-sum problem

Given a set ofn positive integers and another positive integerW, the Subset-Sum Problem is to find that subset whose sum is closest to, without exceeding,W. We present a polynomial approximation scheme for this problem and prove that its worst-case performance dominates that of Johnson's well-known scheme. Research supported by Ministero Pubblica Istruzion, Italy.     

Comparison of the convergence rate of pure greedy and orthogonal greedy algorithms

The following two types of greedy algorithms are considered: the pure greedy algorithm (PGA) and the orthogonal greedy algorithm (OGA). From the standpoint of estimating the rate of convergence on the entire class A ₁(D), the orthogonal greedy algorithm is optimal and significantly exceeds the pure greedy algorithm. The main result in the present paper is the assertion that the situation can also be opposite for separate elements of the class A ₁(D) (and even of the class A ₀(D)): the rate of convergence of the orthogonal greedy algorithm can be significantly lower than the rate of convergence of the pure greedy algorithm.     

Universal bases and greedy algorithms for anisotropic function classes

We suggest a three-step strategy to find a good basis (dictionary) for non-linear m-term approximation. The first step consists of solving an optimization problem of finding a near best basis for a given function class F, when we optimize over a collection D of bases (dictionaries). The second step is devoted to finding a universal basis (dictionary) D _u ∈ D for a given pair (F, D) of collections: F of function classes and D of bases (dictionaries). This means that D_u provides near optimal approximation for each class F from a collection F. The third step deals with constructing a theoretical algorithm that realizes near best m-term approximation with regard to D _u for function classes from F. In this paper we work this strategy out in the model case of anisotropic function classes and the set of orthogonal bases. The results are positive. We construct a natural tensor-product-wavelet-type basis and prove that it is universal. Moreover, we prove that a greedy algorithm realizes near best m-term approximation with regard to this basis for all anisotropic function classes.     

On the existence of weak greedy matching heuristics

We exhibit an exponential number of greedy heuristics for minimum weight perfect matching of complete graphs of n vertices with edge weights satisfying the triangle inequality. The ratio of the weight of an approximate solution obtained by these heuristics to that of an optimal solution is shown to be bounded above by finite valued functions which depend only on n.     

Second-order weak approximations for stratonovich stochastic differential equations

Translated from Lietuvos Matematikos Rinkinys, Vol. 34, No. 2, pp. 226–247, April–June, 1994.