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]