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]

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]

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]

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]