Search

Compressed sensing (CS) seeks to recover an unknown vector with N entries by making far fewer than N measurements; it posits that the number of CS measurements should be comparable to the information content of tile vector, not simply N. CS combines directly the important task of compression with the measurement task. Since its introduction in 2004 there have been hundreds of papers on CS, a large fraction of which develop algorithms to recover a signal from its compressed measurements. Because of the paradoxical nature of CS--exact reconstruction from seemingly undersampled measurements--it is crucial for acceptance of an algorithm that rigorous analyses verify the degree of undersampling the algorithm permits. The restricted isometry property (RIP) has become the dominant tool used for the analysis in such cases. We present here an asymmetric form of RIP that gives tighter bounds than the usual symmetric one. We give the best known bounds on the RIP constants for matrices from the Gaussian ensemble. Our derivations illustrate the way in which the combinatorial nature of CS is controlled. Our quantitative bounds on the RIP allow precise statements as to how aggressively a signal can be undersampled, the essential question for practitioners. We also document the extent to which RIP gives precise information about the true performance limits of CS, by comparison with approaches from high-dimensional geometry. [ABSTRACT FROM AUTHOR]

The Lloyd algorithm originated in the context of optimal quantization and represents a fixed point iteration for computing an optimal quantizer. Reducing average distortion at every step, it constructs a Voronoi partition of the domain and replaces each generator with the centroid of the corresponding Voronoi cell. Optimal quantization is obtained in the case of a centroidal Voronoi tessellation (CVT), which is a special Voronoi tessellation of a domain Ω ϵ ℝd having the property that the generators of the Voronoi diagram are also the centers of mass, with respect to a given density function ? ⩾ 0, of the corresponding Voronoi cells. The Lloyd iteration is currently the most popular and elegant algorithm for computing CVTs and optimal quantizers, but many questions remain about its convergence, especially in d-dimensional spaces (d > 1). In this paper, we prove that any limit point of the Lloyd iteration in any dimensional spaces is nondegenerate provided that Ω is a convex and bounded set and ? belongs to L¹(Ω) and is positive almost everywhere. This ensures that the fixed point map remains closed and hence the standard theory of descent methods guarantees weak global convergence of the Lloyd iteration to the set of nondegenerate fixed point quantizers. While previously only conjectured, the convergence properties of the Lloyd iteration are rigorously justified under such minimal regularity assumptions on the density functional. The results presented in this paper go beyond existing convergence theories for CVTs and optimal quantization related algorithms and should be of interest to both the mathematical and engineering communities. [ABSTRACT FROM AUTHOR]

In this paper, an efficient and stable numerical algorithm for computing multiple saddle points with symmetries is developed by modifying the local minimax method established in [Y. Li and J. Zhou, SIAM J. Sci. Comput. 23 (2001), pp. 840--865; Y. Li and J. Zhou, SIAM J. Sci. Comput., 24 (2002), pp. 840--865]. First an invariant space is defined in a more general sense and a principle of invariant criticality is proved for the generalization. Then the orthogonal projection to the invariant space is used to preserve the invariance and to reduce computational error across iterations. Simple averaging formulas are used for the orthogonal projections. Numerical computations of examples with various symmetries, of which some can and others cannot be characterized by a compact group of linear isomorphisms, are carried out to confirm the theory and to illustrate applications. The mathematical features of various problems demonstrated in these examples fall into two categories: nodal solutions of saddle-point type with large Morse indices and nonradial positive solutions via symmetry breaking in radially symmetric elliptic problems. The new numerical algorithm generates these rather unstable solutions in an efficient and stable way. The existence of many unstable solutions and their behavior found in this paper remain to be investigated. [ABSTRACT FROM AUTHOR]

The Lloyd algorithm originated in the context of optimal quantization and represents a fixed point iteration for computing an optimal quantizer. Reducing average distortion at every step, it constructs a Voronoi partition of the domain and replaces each generator with the centroid of the corresponding Voronoi cell. Optimal quantization is obtained in the case of a centroidal Voronoi tessellation (CVT), which is a special Voronoi tessellation of a domain Ω ϵ ℝd having the property that the generators of the Voronoi diagram are also the centers of mass, with respect to a given density function ? ⩾ 0, of the corresponding Voronoi cells. The Lloyd iteration is currently the most popular and elegant algorithm for computing CVTs and optimal quantizers, but many questions remain about its convergence, especially in d-dimensional spaces (d > 1). In this paper, we prove that any limit point of the Lloyd iteration in any dimensional spaces is nondegenerate provided that Ω is a convex and bounded set and ? belongs to L¹(Ω) and is positive almost everywhere. This ensures that the fixed point map remains closed and hence the standard theory of descent methods guarantees weak global convergence of the Lloyd iteration to the set of nondegenerate fixed point quantizers. While previously only conjectured, the convergence properties of the Lloyd iteration are rigorously justified under such minimal regularity assumptions on the density functional. The results presented in this paper go beyond existing convergence theories for CVTs and optimal quantization related algorithms and should be of interest to both the mathematical and engineering communities. [ABSTRACT FROM AUTHOR]

A well-known generalization of Shannon's sampling theorem states that a bandlimited function can be reconstructed from its periodic nonuniformly spaced samples if the effective sampling rate is at least the Nyquist rate. Analogous to Shannon's sampling theorem this generalization requires that an infinite number of samples be available, which, however, is never the case in practice. Most existing reconstruction methods for periodic nonuniform sampling yield very low order (often not even first order) accuracy when only a finite number of samples is given. In this paper we propose a fast, numerically robust, root-exponential accurate reconstruction method. The efficiency and accuracy of the algorithm is obtained by fully exploiting the sampling structure and utilizing localized Fourier analysis. We discuss applications in analog-to-digital conversion where nonuniform periodic sampling arises in various situations. Finally, we demonstrate the performance of our algorithm by numerical examples. [ABSTRACT FROM AUTHOR]

We present and study a nonconforming domain decomposition method for the discretization of the three-dimensional Stokes problem in the velocity-pressure formulation. The approximation is based on some local mixed finite elements for nonmatching tetrahedral grids. The aim pursued is a systematic construction of the mortared discrete velocity space, the pressure being not subjected to any matching constraints across the interfaces. Using the bubble stabilization techniques, applied in Brezzi and Marini's paper to the three fields method [Math. Cornp., 70 (2001), pp. 911-934], allows us to define an algorithm which is easy to implement. The numerical analysis relies on the pressure-splitting argument of Boland and Nicolaides and allows us to establish an inf-sup condition with a constant that does not depend on the mesh size or on the total number of the subdomains. Then, by the Berger-Scott-Strang lemma written down for our saddle point system we derive optimal accuracy results. [ABSTRACT FROM AUTHOR]

In this paper, we propose a nonoverlapping domain decomposition method for solving the three-dimensional Maxwell equations, based on the edge element discretization. For the Schur complement system on the interface, we construct an efficient preconditioner by introducing two special coarse subspaces defined on the nonoverlapping sub domains. It is shown that the condition number of the preconditioned system grows only polylogarithmically with the ratio between the subdomain diameter and the finite element mesh size but possibly depends on the jumps of the coefficients. [ABSTRACT FROM AUTHOR]

In this paper we show that the lagged diffusivity fixed point algorithm introduced by Vogel and Oman in [SIAM J. Sci. Comput., 17 (1996), pp. 227­238] to solve the problem of total variation denoising, proposed by Rudin, Osher, and Fatemi in [Phys. D, 60 (1992), pp. 259­268], is a particular instance of a class of algorithms introduced by Voss and Eckhardt in [Computing, 25 (1980), pp. 243­251], whose origins can be traced back to Weiszfeld's original work for minimizing a sum of Euclidean lengths [Tôhoku Math. J., 43 (1937), pp. 355­386]. There have recently appeared several proofs for the convergence of this algorithm [G. Aubert et al., Technical report 94-01, Informatique, Signaux et Systèmes de Sophia Antipolis, 1994], [A. Chambolle and P.-L. Lions, Technical report 9509, CEREMADE, 1995], and [D. C. Dobson and C. R. Vogel, SIAM J. Numer. Anal., 34 (1997), pp. 1779­1791]. Here we present a proof of the global and linear convergence using the framework introduced in [H. Voss and U. Eckhart, Computing, 25 (1980), pp. 243­251] and give a bound for the convergence rate of the fixed point iteration that agrees with our experimental results. These results are also valid for suitable generalizations of the fixed point algorithm. [ABSTRACT FROM AUTHOR]

Fast Marching Methods are numerical schemes for computing solutions to the nonlinear Eikonal equation and related static. Hamilton­Jacobi equations. Based on entropy-satisfying upwind schemes and fast sorting techniques, they yield consistent, accurate, and highly efficient algorithms. They are optimal in the sense that the computational complexity of the algorithms is O(N log N), where N is the total number of points in the domain. The schemes are of use in a variety of applications, including problems in shape offsetting, computing distance from compiles curves and surfaces, shape-from-shading, photolithographic development, computing first arrivals in seismic travel times, construction of shortest geodesies on surfaces, optimal path planning around obstacles, and visibility and reflection calculations. In this paper, were review the development of these techniques, including the theoretical and numerical underpinnings; provide details of the computational schemes, including higher order versions; and demonstrate the techniques in a collection of different areas. [ABSTRACT FROM AUTHOR]

This paper is concerned with a classical denoising and deblurring problem in image recovery. Our approach is based on a variational method. By using the Legendre­Fenchel transform, we show how the nonquadratic criterion to be minimized can be split into a sequence of half-quadratic problems easier to solve numerically. First we prove an existence and uniqueness result, and then we describe the algorithm for computing the solution and we give a proof of convergence. Finally, we present some experimental results for synthetic and real images. [ABSTRACT FROM AUTHOR]

A cell-centered finite volume method is proposed to approximate numerically the solution to the steady convection-diffusion equation on unstructured meshes of $d$-simplexes, where $d\geq 2$ is the spatial dimension. The method is formally second-order accurate by means of a piecewise linear reconstruction within each cell and at mesh vertices. An algorithm is provided to calculate nonnegative and bounded weights. Face gradients, required to discretize the diffusive fluxes, are defined by a nonlinear strategy that allows us to demonstrate the existence of a maximum principle. Finally, a set of numerical results documents the performance of the method in treating problems with internal layers and solutions with strong gradients. [ABSTRACT FROM AUTHOR]

Using Smolyak's construction [S. A. Smolyak, Dokl. Akad. Nauk SSSR, 4 (1963), pp. 240--243], we derive a new algorithm for approximating multivariate functions over bounded or unbounded regions in $\R^s$ with the error measured in a weighted L1-norm. We provide upper bounds for the algorithm's cost and error for a class of functions whose mixed first order partial derivatives are bounded in the L1-norm. In particular, we prove that the error and the cost (measured in terms of the number of function evaluations) satisfy the relation $$ error \le \frac{s\,\exp\big(\frac1{12(s-1)}\big)}{(s-1)\pi}\, \left(\frac{e\,\ln(\mbox{cost})}{(s-1)\sqrt{2}\ln(2)}\right)^{2(s-1)}\, \frac1{{cost}} $$ whenever the cost is sufficiently large relative to the number s of variables. More specifically, the inequality holds when $q\ge2(s-1)$, where q is a special parameter defining the refinement level in Smolyak's algorithm, and hence the number of function evaluations used by the algorithm. We also discuss extensions of the results to the spaces with the derivatives bounded in Lp-norms. [ABSTRACT FROM AUTHOR]

Applied mathematics and scientific computation come together most beautifully when sophisticated mathematics is used to generate effective algorithms for challenging real-world problems. This combination can be even more splendid when there is a geometric underpinning to the process. Multigrid methods, which were pioneered three to four decades ago, beginning with the papers of Fedorenko in the 1960s and the seminal paper by Brandt in 1977, combine all of these aspects. Their conceptual framework, most easily understood by correspondence to finer and coarser physical grids of discretized differential equations, has led to one of the most powerful tools in scientific computation. Originally designed for elliptic partial differential equations arising in computational fluid dynamics, multigrid methods have now been extended to algebraic multigrid methods and multilevel methods that have been successfullly applied to problems in a stunningly wide range of areas, such as image reconstruction, optimization, quantum chromodynamics, and integral equations. Algebraic multigrid methods are fascinating because they provide the advantages of multigrid using an algebraic derivation, in cases where a geometric underpinning for a method is not available. As with all multigrid methods, however, they have required some knowledge or assumptions about the near-nullspace of the multigrid operator. As the problem is relaxed to coarser grids, it is crucial to the success of the method that these critical error components can be approximated accurately. The SIGEST paper in this issue, "Adpative Smoothed Aggregation ($\alpha$SA) Multigrid" by M. Brezina, R. Falgout, S. MacLachlan, T. Manteuffel, S. McCormick, and J. Ruge, is the first paper to achieve an algebraic multigrid solver that does not require a priori knowledge of the near-nullspace of the multigrid operator. Instead, the authors show how to generate this information as part of the algorithm, through an adaptive process that uses the multigrid method to determine near-kernel components and adjust the method as it proceeds. In fact, in the terminology of the authors, they use the natural weakness of the method to adaptively determine this information. This paper, which first appeared in 2004 in the SIAM Journal on Scientific Computing, has been judged by the editors of that journal to be an outstanding contribution to that field. The authors have taken the opportunity of the appearance of this paper in SIAM Review to broaden its accessibility. They have included a brief description of the general multigrid principles and terminology, geared towards problems for which algebraically smooth error is not smooth in the traditional geometric sense, such as those considered in the paper. They also have included a list of several principles on which a design of adaptive multigrid method should be based. These are applicable to a general underlying multigrid method, not just for the smoothed aggregation method studied in the paper. Finally, they have added some stunning color illustrations that depict aggregates over unstructured two- and three-dimensional meshes. The result is a paper that multigrid experts can appreciate for its deep contributions, and that all readers can enjoy for its clear, careful presentation and introduction to the modern world of algebraic multrid methods. [ABSTRACT FROM AUTHOR]

Computational convex analysis algorithms have been rediscovered several times in the past by researchers from different fields. To further communications between practitioners, we review the field of computational convex analysis, which focuses on the numerical computation of fundamental transforms arising from convex analysis. Current models use symbolic, numeric, and hybrid symbolic-numeric algorithms. Our objective is to disseminate widely the most efficient numerical algorithms useful for applications in image processing (computing the distance transform, the generalized distance transform, and mathematical morphology operators), partial differential equations (solving Hamilton--Jacobi equations and using differential equations numerical schemes to compute the convex envelope), max-plus algebra (computing the equivalent of the fast Fourier transform), multifractal analysis, etc. The fields of applications include, among others, computer vision, robot navigation, thermodynamics, electrical networks, medical imaging, and network communication [ABSTRACT FROM AUTHOR]

A BDDC (balancing domain decomposition by constraints) method is developed for elliptic equations, with discontinuous coefficients, discretized by mortar finite element methods for geometrically nonconforming partitions in both two and three space dimensions. The coarse component of the preconditioner is defined in terms of one mortar constraint for each edge/face, which is the intersection of the boundaries of a pair of subdomains. A condition number bound of the form C maxi{(1 + log(Hi/hi))2} is established under certain assumptions on the geometrically nonconforming subdomain partition in the three-dimensional case. Here Hi and hi are the subdomain diameters and the mesh sizes, respectively. In the geometrically conforming case and the geometrically nonconforming cases in two dimensions, no assumptions on the subdomain partition are required. This BDDC preconditioner is also shown to be closely related to the Neumann-Dirichlet version of the FETI-DP algorithm. The results are illustrated by numerical experiments which confirm the theoretical results. [ABSTRACT FROM AUTHOR]

We derive two reformulations of the C¹ Hermite subdivision scheme introduced by Merrien. One where we separate computation of values and derivatives and one based of refinement of a control polygon. We show that the latter leads to a subdivision matrix which is totally positive. Based on this we give algorithms for constructing subdivision curves that preserve positivity, monotonicity, and convexity. [ABSTRACT FROM AUTHOR]

We consider the behavior of certain adaptive timestepping methods, based upon embedded explicit Runge--Kutta pairs, when applied to dissipative ODEs. It has been observed numerically that the standard local error controls can impart desirable stability properties, but this has been rigorously verified only for very special, low-order, Runge--Kutta pairs. The rooted-tree expansion of a certain quadratic form, central to the stability theory of Runge--Kutta methods, is derived. This, together with key assumptions on the sequence of accepted time-steps and the local error estimate, provides a general explanation for the observed stability of such algorithms on dissipative problems. Under these assumptions, which are expected to hold for "typical" numerical trajectories, two different results are proved. First, for a large class of embedded Runge--Kutta pairs of order $(1,2)$, controlled on an error-per-unit-step basis, all such numerical trajectories will eventually enter a particular bounded set. This occurs for sufficiently small tolerances independent of the initial conditions. Second, for pairs of arbitrary orders $(p-1,p)$, operating under either error-per-step or error-per-unit-step control, similar results are obtained when an additional structural assumption (that should be valid for many cases of interest) is imposed on the dissipative vector field. Numerical results support both the analysis and the assumptions made. [ABSTRACT FROM AUTHOR]

Some tally methods for preferential elections are discussed from the following point of view: How well do they respect a wish from the voter that subsidiary votes in the ballot cannot hurt the chances of the ballot's top-ranked candidate? The standard variation of single transferable votes (STV) is constructed to obey this principle, but other defects show up, in particular nonmonotonicity, premature eliminations, and free rides. The tax cut algorithm is also an essential part of Meek's modification of STV. Properties of the algorithm are established and other ways to apply it are considered, with the purpose of reducing the election method's weaknesses without losing too many of its strengths. [ABSTRACT FROM AUTHOR]

We introduce a nonoverlapping variant of the Schwarz waveform relaxation algorithm for wave propagation problems with variable coefficients in one spatial dimension. We derive transmission conditions which lead to convergence of the algorithm in a number of iterations equal to the number of sub domains, independently of the length of the time interval. These optimal transmission conditions are in general nonlocal, but we show that the nonlocality depends on the time interval under consideration, and we introduce time windows to obtain optimal performance of the algorithm with local transmission conditions in the case of piecewise constant wave speed. We show that convergence in two iterations can be achieved independently of the number of subdomains in that case. The algorithm thus scales optimally with the number of sub domains, provided the time windows are chosen appropriately. For continuously varying coefficients we prove convergence of the algorithm with local transmission conditions using energy estimates. We then introduce a finite volume discretization which permits computations on nonmatching grids, and we prove convergence of the fully discrete Schwarz waveform relaxation algorithm. We finally illustrate our analysis with numerical experiments. [ABSTRACT FROM AUTHOR]

It has been shown recently that optimization-based nonoverlapping domain decom- position algorithms are connected to many well-known algorithms. Using a gradient-type iterative strategy for the optimization problem, we present further discussion on how to develop various algo- rithms that can integrate subdomain solvers into a solver for the problem in the whole domain. In particular, the algorithms we discuss can be used to develop efficient solvers of multidisciplinary prob- lems which are constructed using existing subdomain solvers without the need for making changes in the latter. [ABSTRACT FROM AUTHOR]

The iterative substructuring methods, also known as Schur complement methods, form one of two important families of domain decomposition algorithms. They are based on a partitioning of a given region, on which the partial differential equation is defined, into nonoverlapping substructures. The preconditioners of these conjugate gradient methods are then given in terms of local problems, defined on individual substructures and pairs of substructures, and, in addition, a global problem of low dimension. An iterative method of this kind is introduced for the lowest order Raviart­Thomas finite elements in three dimensions and it is shown that the condition number of the relevant operator is independent of the number of substructures and grows only as the square of the logarithm of the number of unknowns associated with an individual substructure. The theoretical bounds are confirmed by a series of numerical experiments. [ABSTRACT FROM AUTHOR]

Problems with singular perturbations exhibit solutions with strong boundary layers and other types of local behavior. Such features lend themselves to adaptive solution methods. The quality of any adaptive algorithm ultimately rests on the reliability and robustness of the a posteriori error control. An estimator that has proved to be one of the most reliable is the equilibrated residual method. The main property of the estimator is that it bounds the true error from above. However, the method is not robust in the singularly perturbed limit. The current work generalizes the error estimator based on the equilibrated residuals and coincides with the standard method in the unperturbed limit. It is shown that the new method is robust in the singularly perturbed limit while maintaining reliability, yielding a guaranteed upper bound on the true error. Finally, the application of the estimator to the problem of controlling the spatial error in Rothe's method for the time discretization of a simple parabolic problem is included. [ABSTRACT FROM AUTHOR]

An iterative method is proposed to solve the Schrödinger eigenvalue problem in a wavelet framework. Orthonormal wavelets are used to represent the corresponding operator as a sparse band matrix. This representation, called the nonstandard (NS) form, is obtained by means of the Beylkin­Coifman­Rokhlin (BCR) algorithm and simplifies the numerical calculations. Problems due to the one-dimensional mathematical model and to the discretization process receive special attention. [ABSTRACT FROM AUTHOR]