Surface based 3D shape analysis plays a fundamental role in computer vision and medical imaging. This work proposes to use optimal mass transport map for shape matching and comparison, focusing on two important applications including surface registration and shape space. The computation of the optimal mass transport map is based on Monge-Brenier theory, in comparison to the conventional method based on Monge-Kantorovich theory, this method significantly improves the efficiency by reducing computational complexity from O(n ² ) to O(n). For surface registration problem, one commonly used approach is to use conformal map to convert the shapes into some canonical space. Although conformal mappings have small angle distortions, they may introduce large area distortions which are likely to cause numerical instability thus resulting failures of shape analysis. This work proposes to compose the

We study how to characterize the families of paths between any two nodes s, t in a sensor network with holes. Two paths that can be deformed to one another through local changes are called homotopy equivalent. Two paths that pass around holes in different ways have different homotopy types. With a distributed algorithm we compute an embedding of the network in hyperbolic space by using Ricci flow such that paths of different homotopy types are mapped naturally to paths connecting s with different images of t. Greedy routing to a particular image is guaranteed with success to find a path with a given homotopy type. This leads to simple greedy routing algorithms that are resilient to both local link dynamics and large scale jamming attacks and improve load balancing over previous greedy routing algorithms.

We present a novel area-preservation mapping/flattening method using the optimal mass transport technique, based on the Monge-Brenier theory. Our optimal transport map approach is rigorous and solid in theory, efficient and parallel in computation, yet general for various applications. By comparison with the conventional Monge-Kantorovich approach, our method reduces the number of variables from O(n²) to O(n), and converts the optimal mass transport problem to a convex optimization problem, which can now be efficiently carried out by Newton's method. Furthermore, our framework includes the area weighting strategy that enables users to completely control and adjust the size of areas everywhere in an accurate and quantitative way. Our method significantly reduces the complexity of the problem, and improves the efficiency, flexibility and scalability during visualization. Our framework, by combining

Greedy forwarding with geographical locations in a wireless sensor network may fail at a local minimum. In this paper we propose to use conformal mapping to compute a new embedding of the sensor nodes in the plane such that greedy forwarding with the virtual coordinates guarantees delivery. In particular, we extract a planar triangulation of the sensor network with non-triangular faces as holes, by either using the nodes' location or using a landmark-based scheme without node location. The conformal map is computed with Ricci flow such that all the non-triangular faces are mapped to perfect circles. Thus greedy forwarding will never get stuck at an intermediate node. The computation of the conformal map and the virtual coordinates is performed at a preprocessing phase and can be implemented by local gossip-style computation. The method applies to both unit disk graph models and quasi-unit disk graph

Variational models with \ell_1-norm based regularization, in particular total variation (TV) and its variants, have long been known to offer superior image restoration quality, but processing speed remained a bottleneck, preventing their widespread use in the practice of color image processing. In this paper, by extending the grayscale image deblurring algorithm proposed in [Y. Wang, J. Yang, W. Yin, and Y. Zhang, <i>SIAM J. Imaging Sci.</i>, 1 (2008), pp. 248272], we construct a simple and efficient algorithm for multichannel image deblurring and denoising, applicable to both within-channel and cross-channel blurs in the presence of additive Gaussian noise. The algorithm restores an image by minimizing an energy function consisting of an \ell_1-norm fidelity term and a regularization term that can be either TV, weighted TV, or regularization functions based on higher-order derivatives. Specifically, we use a multichannel

Recent compressive sensing results show that it is possible to accurately reconstruct certain compressible signals from relatively few linear measurements via solving nonsmooth convex optimization problems. In this paper, we propose the use of the alternating direction method - a classic approach for optimization problems with separable variables (D. Gabay and B. Mercier, A dual algorithm for the solution of nonlinear variational problems via finite-element approximations, Computer and Mathematics with Applications, vol. 2, pp. 17-40, 1976; R. Glowinski and A. Marrocco, Sur lapproximation par elements finis dordre un, et la resolution par penalisation-dualite dune classe de problemes de Dirichlet nonlineaires, Rev. Francaise dAut. Inf. Rech. Oper., vol. R-2, pp. 41-76, 1975) - for signal reconstruction from partial Fourier (i.e., incomplete frequency) measurements. Signals are reconstructed as minimizers of

The matrix completion problem is to recover a low-rank matrix from a subset of its entries. The main solution strategy for this problem has been based on nuclear-norm minimization which requires computing singular value decompositionsa task that is increasingly costly as matrix sizes and ranks increase. To improve the capacity of solving large-scale problems, we propose a low-rank factorization model and construct a nonlinear successive over-relaxation (SOR) algorithm that only requires solving a linear least squares problem per iteration. Extensive numerical experiments show that the algorithm can reliably solve a wide range of problems at a speed at least several times faster than many nuclear-norm minimization algorithms. In addition, convergence of this nonlinear SOR algorithm to a stationary point is analyzed.

We present a framework for solving the large-scale \ell_1-regularized convex minimization problem:<div class="gsh_dspfr">\ell_1

We introduce a new iterative regularization procedure for inverse problems based on the use of Bregman distances, with particular focus on problems arising in image processing. We are motivated by the problem of restoring noisy and blurry images via variational methods by using total variation regularization. We obtain rigorous convergence results and effective stopping criteria for the general procedure. The numerical results for denoising appear to give significant improvement over standard models, and preliminary results for deblurring/denoising are very encouraging.

We consider the solution of the rational matrix equations, or generalized algebraic Riccati equations with rational terms, arising in stochastic optimal control in continuous- and discrete-time. Fixed-point iteration and (modified) Newton's methods will be considered. In particular, the convergence results of a new modified Newton's method, for both continuous- and discrete-time rational Riccati equations, will be presented.

We propose a structure-preserving doubling algorithm for a quadratic eigenvalue problem arising from the stability analysis of time-delay systems. We are particularly interested in the eigenvalues on the unit circle, which are difficult to estimate. The convergence and backward error of the algorithm are analyzed and three numerical examples are presented. Our experience shows that our algorithm is efficient in comparison to the few existing approaches for small to medium size problems.

We study the generalized eigenvalue problems (GEPs) derived from modeling the surface acoustic wave in piezoelectric materials with periodic inhomogeneity. The eigenvalues appear in the reciprocal pairs due to periodic boundary conditions in the modeling. By transforming the GEP into a T-palindromic quadratic eigenvalue problem (TPQEP), the reciprocal relationship of the eigenvalues can be maintained. In this paper, we outline four recently developed structure-preserving algorithms, SA, SDA, TSHIRA and GTSHIRA, for solving the TPQEP. Numerical comparisons on the accuracy and the computational costs of these algorithm are presented. The eigenvalues close to unit circle on the complex plane are of interest in the area of filter and sensor designs. Our numerical results show that the Arnoldi-type structure-preserving algorithms TSHIRA and GTSHIRA with re-symplectic and re-bi-isotropic processes

Calculation of band structure of three dimensional photonic crystals amounts to solving large-scale Maxwell eigenvalue problems, which are notoriously challenging due to high multiplicity of zero eigenvalue. In this paper, we try to address this problem in such a broad context that band structure of three dimensional isotropic photonic crystals with all 14 Bravais lattices can be efficiently computed in a unified framework. We uncover the delicate machinery behind several key results of our work and on the basis of this new understanding we drastically simplify the derivations, proofs and arguments in our framework. In this work particular effort is made on reformulating the Bloch boundary condition for all 14 Bravais lattices in the redefined orthogonal coordinate system, and establishing eigen-decomposition of discrete partial derivative operators by systematic use of commutativity among them, which has been overlooked previously, and reducing eigen-decomposition of double-curl operator to the canonical form of a 3x3 complex skew-symmetric matrix under unitary congruence. With the validity of the novel nullspace free method in the broad context, we perform some calculations on one benchmark system to demonstrate the accuracy and efficiency of our algorithm.

For the steady-state solution of a differential equation from a one-dimensional multistate model in transport theory, we shall derive and study a nonsymmetric algebraic Riccati equation <i>B</i> <i>XF</i> <i>F</i>⁺<i>X</i> + <i>XB</i>⁺<i>X</i> = 0, where <i>F</i> (<i>I</i> <i>F</i>)<i>D</i> and <i>B</i> <i>BD</i> with positive diagonal matrices <i>D</i> and possibly low-ranked matrices <i>F</i> and <i>B</i>. We prove the existence of the minimal positive solution <i>X</i>^* under a set of physically reasonable assumptions and study its numerical computation by fixed-point iteration, Newtons method and the doubling algorithm. We shall also study several special cases. For example when <i>B</i> and <i>F</i> are low ranked then X*=(i=14UiViT) with low-ranked <i>U_i</i> and <i>V_i</i> that can be computed using more efficient iterative processes. Numerical examples will be given to illustrate our theoretical results.

For the steady-state solution of an integraldifferential equation from a two-dimensional model in transport theory, we shall derive and study a nonsymmetric algebraic Riccati equation B--XF--F+ X+ XB+ X= 0, where F I-s PD, B-(b I+ s P) D-and B+ b I+ s PD+ with a nonnegative matrix P, positive diagonal matrices D, and nonnegative parameters f, b b/(1-f) and s s/(1-f). We prove the existence of the minimal nonnegative solution X under the physically reasonable assumption f+ b+ s P (D++ D-)&lt; 1, and study its numerical computation by fixed-point iteration, Newtons method and doubling. We shall also study several special cases; eg when b = 0 and P is low-ranked, then X= s 2 UV is low-ranked and can be computed using more efficient iterative processes in U and V. Numerical examples will be given to illustrate our theoretical results.

We propose an efficient eigensolver for computing densely distributed spectra of the two-dimensional transmission eigenvalue problem (TEP), which is derived from Maxwell's equations with Tellegen media and the transverse magnetic mode. The governing equations, when discretized by the standard piecewise linear finite element method, give rise to a large-scale quadratic eigenvalue problem (QEP). Our numerical simulation shows that half of the positive eigenvalues of the QEP are densely distributed in some interval near the origin. The quadratic JacobiDavidson method with a so-called non-equivalence deflation technique is proposed to compute the dense spectrum of the QEP. Extensive numerical simulations show that our proposed method processes the convergence efficiently, even when it needs to compute more than 5000 desired eigenpairs. Numerical results also illustrate that the computed

We consider the solution of large-scale Lyapunov and Stein equations. For Stein equations, the well-known Smith method will be adapted, with A_k = A^{2^k} not explicitly computed but in the recursive form A_k = A^{2^k}, and the fast growing but diminishing components in the approximate solutions truncated. Lyapunov equations will be first treated with the Cayley transform before the Smith method is applied. For algebraic equations with numerically low-ranked solutions of dimension <i>n</i>, the resulting algorithms are of an efficient <i>O</i>(<i>n</i>) computational complexity and memory requirement per iteration and converge essentially quadratically. An application in the estimation of a lower bound of the condition number for continuous-time algebraic Riccati equations is presented, as well as some numerical results.

METHODS AND APPLICATIONS OF ANALYSIS. 2000 International Press Vol. 7, No. 3, pp. 591-604, September 2000 012

Surface segmentation is a fundamental problem in computer graphics. It has various applications such as metamorphosis, surface matching, surface compression, 3D shape retrieval, texture mapping, etc. All orientable surfaces are Riemann surfaces, and admit conformal structures. This paper introduces a novel surface segmentation algorithm based on its conformal structure. Each segment can be conformally mapped to a planar rectangle, and the transition maps are planar translations. The segmentation is intrinsic to the surface, independent of the embedding, and consistent for surfaces with similar geometries. By using segmentation based on conformal structure, the mapping between surfaces with arbitrary topologies can be constructed explicitly. The method is rigorous, efficient and automatic. The segmentation can be applied to surface morphing, construct conformal geometry image, convert mesh to Spline

A multilevel quality-guided phase unwrapping algorithm for real-time 3D shape measurement is presented. The quality map is generated from the gradient of the phase map. Multilevel thresholds are used to unwrap the phase level by level. Within the data points in each level, a fast scan-line algorithm is employed. The processing time of this algorithm is approximately 18.3 ms for an image size of 640480 pixels in an ordinary computer. We demonstrate that this algorithm can be implemented into our real-time 3D shape measurement system for real-time 3D reconstruction. Experiments show that this algorithm improves the previous scan-line phase unwrapping algorithm significantly although it reduces its processing speed slightly.

We propose a computational framework named iterative local adaptive majorize-minimization (I-LAMM) to simultaneously control algorithmic complexity and statistical error when fitting high dimensional models. I-LAMM is a two-stage algorithmic implementation of the local linear approximation to a family of folded concave penalized quasi-likelihood. The first stage solves a convex program with a crude precision tolerance to obtain a coarse initial estimator, which is further refined in the second stage by iteratively solving a sequence of convex programs with smaller precision tolerances. Theoretically, we establish a phase transition: the first stage has a sublinear iteration complexity, while the second stage achieves an improved linear rate of convergence. Though this framework is completely algorithmic, it provides solutions with optimal statistical performances and controlled algorithmic complexity for a large family

We propose a numerically efficient algorithm for simulating the multi-color optical self-focusing phenomena in nematic liquid crystals. The propagation of the nematicon is modeled by a parabolic wave equation coupled with a nonlinear elliptic partial differential equation governing the angle between the crystal and the direction of propagation. Numerically, the paraxial parabolic wave equation is solved by a fast Huygens sweeping method, while the nonlinear elliptic PDE is handled by the alternating direction explicit (ADE) method. The overall algorithm is shown to be numerically efficient for computing high frequency beam propagations.

We propose a computational efficient yet simple numerical algorithm to solve the surface eikonal equation on general implicit surfaces. The method is developed based on the embedding idea and the fast sweeping methods. We first approximate the solution to the surface eikonal equation by the Euclidean weighted distance function defined in a tubular neighbourhood of the implicit surface, and then apply the efficient fast sweeping method to numerically compute the corresponding viscosity solution. Unlike some other embedding methods which require the radius of the computational tube satisfies h = O ( x ) for some h = O ( x ) , our approach allows h = O ( x ) . This implies that the total number of grid points in the computational tube is optimal and is given by h = O ( x ) for a co-dimensional one surface in h = O ( x ) . The method can be easily extended to general static HamiltonJacobi equation defined on implicit

We propose a new and simple discretization, named the modified virtual grid difference (MVGD), for numerical approximation of the Laplace--Beltrami (LB) operator on manifolds sampled by point clouds. The key observation is that both the manifold and a function defined on it can both be parametrized in a local Cartesian coordinate system and approximated using least squares. Based on the above observation, we first introduce a local virtual grid with a scale adapted to the sampling density centered at each point. Then we propose a modified finite difference scheme on the virtual grid to discretize the LB operator. Instead of using the local least squares values on all virtual grid points like the typical finite difference method, we use the function value explicitly at the grid located at the center (coinciding with the data point). The new discretization provides more diagonal dominance to the resulting linear system and

The equilibrium metric for minimizing a continuous congested traffic model is the solution of a variational problem involving geodesic distances. The continuous equilibrium metric and its associated variational problem are closely related to the classical discrete Wardrops equilibrium. We propose an adjoint state method to numerically approximate continuous traffic congestion equilibria through the continuous formulation. The method formally derives an adjoint state equation to compute the gradient descent direction so as to minimize a nonlinear functional involving the equilibrium metric and the resulting geodesic distances. The geodesic distance needed for the state equation is computed by solving a factored eikonal equation, and the adjoint state equation is solved by a fast sweeping method. Numerical examples demonstrate that the proposed adjoint state method produces desired equilibrium metrics and