Fast Algorithms for Nonlinear Problems
for Modern Applications

6 July 2017
Hong Kong Baptist University

Time: 13:00pm -19:10pm
Venue: FSC1217, Fong Shu Chuen Building, Ho Sin Hang Campus

Cai, Jianfeng, The Hong Kong University of Science and Technology, Hong Kong
Glowinski, Roland, Hong Kong Baptist University, Hong Kong
Kwok, Felix, Hong Kong Baptist University, Hong Kong
Liu, Haixia, The Hong Kong University of Science and Technology, Hong Kong
Lui, Ronald, The Chinese University of Hong Kong, Hong Kong
Shi, Zuoqiang, Tsinghua University, Beijng, China
Wang, Xiaoping, The Hong Kong University of Science and Technology, Hong Kong
Yin, Ke/Tai, Xuecheng, Hong Kong Baptist University, Hong Kong
Zeng, Tieyong, Hong Kong Baptist University, Hong Kong



Lui, Ronald

Abstract: In recent decades, the use of 3D point clouds has been widespread in computer industry. The development of techniques in analysing point clouds is increasingly important. In particular, mapping of point clouds has been a challenging problem. In this talk, I will introduce a discrete analogue of the Teichmuller extremal mappings, which guarantees uniform conformality distortions, on point cloud surfaces. Based on the discrete analogue, we develop a novel method called TEMPO for computing Teichmuller extremal mappings between feature-endowed point clouds. Using our proposed method, the Teichmuller metric can be computed for evaluating the dissimilarity between point clouds. Consequently, our algorithm enables accurate shape recognition and classification. The idea can also be applied to geometry processing of 3D shapes. Experimental results will be demonstrated to show the effectiveness of our proposed method.

Coffee Break

Wang, Xiaoping

Abstract: We proposed an efficient iterative thresholding method for multi-phase image segmentation. The algorithm is based on minimizing piecewise constant Mumford-Shah functional in which the contour length (or perimeter) is approximated by a non-local multi-phase energy. The minimization problem is solved by an iterative method. Each iteration consists of computing simple convolutions followed by a thresholding step. The algorithm is easy to implement and has the optimal complexity O(N log N) per iteration. We also show that the iterative algorithm has the total energy decaying property.

Shi, Zuoqiang

Abstract: In this talk, I will introduce a novel low dimensional manifold model for image processing problem. This model is based on the observation that for many natural images, the patch manifold usually has low dimension structure. Then, we use the dimension of the patch manifold as a regularization to recover the original image. Using some formula in differential geometry, this problem is reduced to solve Laplace-Beltrami equation on manifold. The Laplace-Beltrami equation is solved by the point integral method. Numerical tests show that this method gives very good results in image inpainting, denoising and super-resolution problem. (This is joint work with Stanley Osher and Wei Zhu).


Liu, Haixia

Abstract: The phase retrieval problem is a fundamental problem in many applications, e.g., imaging, optics, communication, audio signal processing and more. It is to recover the signal vector x \in Cd from a set of N measurements bn=|fn* \tilde{x} |2, n = 1, 2, ..., N, where {fn}(n=1)N forms a frame of Cd.

In this talk we develop an algorithm for phase retrieval that is both highly efficient and works for very general measurement matrices. Our algorithm is based on the ideas of convex relaxation in PhaseLift and the alternating minimization algorithm used for low rank matrix completion. By splitting the variables, our algorithm solves a bi-variant optimization problem whose objective is quadratic in one of the variables with the other fixed. The convergence for any initialization is provided. Since a larger step size is allowed due to the smaller Hessian, the alternating gradient descent algorithm converges faster than the gradient descent algorithm (known as the Wirtinger flow algorithm) applied to the quartic objective without splitting the variables. Numerical results illustrate that our proposed algorithm needs less iterations than Wirtinger flow to achieve the same accuracy. (Joint work with Prof. Jian-Feng Cai and Prof. Yang Wang.)

Coffee Break

Zeng, Tieyong

Abstract: Image recovery is fundamental in the domain of image processing. We present some recent progress in this area.

Kwok, Felix

Abstract: In this talk, we consider a class of domain decomposition methods, known as waveform relaxation (WR) methods, for solving time-dependent PDEs numerically on many different processors in parallel. WR methods are distinctive in that a typical subdomain problem is posed in both space and time; each iteration requires the parallel solution of these space-time subproblems, followed by an exchange of interface data defined over the whole time window. An often cited advantage of WR methods is that they allow each subdomain to use a different spatial and temporal grid that is adapted to the dynamics of the local subproblem.

In this talk, I will first present some new results on the convergence of WR methods of the Neumann-Neumann type. Next, I will discuss two ways of introducing parallelism in time to the basic WR method. The first approach uses a fixed time-window size and yields an algorithm that is mathematically equivalent to the original WR method. The second one, on the other hand, chooses time-window size dynamically based on how many free processors are available; this leads to a method with improved convergence behaviour. We demonstrate the effectiveness of both approaches by comparing their running times against those obtained from classical time-stepping methods, where the same number of processors is used to parallelize in space only.

Cai, Jianfeng

Abstract: We present a framework of non-convex methods for reconstructing a low rank matrix from its limited information, which arises from numerous practical applications in machine learning, imaging, signal processing, computer vision, etc. Our methods will be applied to several concrete example problems such as matrix completion, phase retrieval, and spectral compressed sensing with super resolution. We will also provide theoretical guarantee of our methods for the convergence to the correct low-rank matrix.