Shingyu Leung

Ke Wei, Jian-Feng Cai, Tony F. Chan et al.

We establish theoretical recovery guarantees of a family of Riemannian optimization algorithms for low rank matrix recovery, which is about recovering an $m\times n$ rank $r$ matrix from $p < mn$ number of linear measurements. The algorithms are first interpreted as iterative hard thresholding algorithms with subspace projections. Based on this connection, we show that provided the restricted isometry constant $R_{3r}$ of the sensing operator is less than $C_κ/\sqrt{r}$, the Riemannian gradient descent algorithm and a restarted variant of the Riemannian conjugate gradient algorithm are guaranteed to converge linearly to the underlying rank $r$ matrix if they are initialized by one step hard thresholding. Empirical evaluation shows that the algorithms are able to recover a low rank matrix from nearly the minimum number of measurements necessary.

Ke Wei, Jian-Feng Cai, Tony F. Chan et al.

We study the Riemannian optimization methods on the embedded manifold of low rank matrices for the problem of matrix completion, which is about recovering a low rank matrix from its partial entries. Assume $m$ entries of an $n\times n$ rank $r$ matrix are sampled independently and uniformly with replacement. We first prove that with high probability the Riemannian gradient descent and conjugate gradient descent algorithms initialized by one step hard thresholding are guaranteed to converge linearly to the measured matrix provided \begin{align*} m\geq C_κn^{1.5}r\log^{1.5}(n), \end{align*} where $C_κ$ is a numerical constant depending on the condition number of the underlying matrix. The sampling complexity has been further improved to \begin{align*} m\geq C_κnr^2\log^{2}(n) \end{align*} via the resampled Riemannian gradient descent initialization. The analysis of the new initialization procedure relies on an asymmetric restricted isometry property of the sampling operator and the curvature of the low rank matrix manifold. Numerical simulation shows that the algorithms are able to recover a low rank matrix from nearly the minimum number of measurements.

Meng Wang, Shingyu Leung, Hongkai Zhao

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 (coincided with the data point). The new discretization provides more diagonal dominance to the resulting linear system and improves its conditioning. We show that the linear system can be robustly, efficiently and accurately solved by existing fast solver such as the Algebraic Multigrid (AMG) method. We will present numerical tests and comparison with other exiting methods to demonstrate the effectiveness and the performance of the proposed approach.

Wenbin Li, Ken K. T. Hung, Shingyu Leung

We present a novel multilayer level-set method (MLSM) for eikonal-based first-arrival traveltime tomography. Unlike classical level-set approaches that rely solely on the zero-level set, the MLSM represents multiple phases through a sequence of $i_n$-level sets ($n = 0, 1, 2, \cdots$). Near each $i_n$-level set, the function is designed to behave like a local signed-distance function, enabling a single level-set formulation to capture arbitrarily many interfaces and subregions. Within this Eulerian framework, first-arrival traveltimes are computed as viscosity solutions of the eikonal equation, and Fréchet derivatives of the misfit are obtained via the adjoint state method. To stabilize the inversion, we incorporate several regularization strategies, including multilayer reinitialization, arc-length penalization, and Sobolev smoothing of model parameters. In addition, we introduce an illumination-based error measure to assess reconstruction quality. Numerical experiments demonstrate that the proposed MLSM efficiently recovers complex discontinuous slowness models with multiple phases and interfaces.

Shingyu Leung

We develop a numerical scheme for solving the advection equation of $\mathbb{S}^2$-valued functions of real variables, which models the time-evolution of a $\mathbb{S}^2$-valued mapping on the real line by a known velocity field. The idea is to extend the semi-Lagrangian method for the linear scalar advection equation. We first construct the backward flow map between two adjacent time levels and then interpolate the discrete ordered data of $\mathbb{S}^2$. To handle $\mathbb{S}^2$-functions which have kinks or sharp discontinuity in their components, we incorporate the \textit{Spherical Essentially Non-Oscillatory} (SENO) interpolation method, which effectively reduces the spurious oscillations in high-order reconstructions. We will show multiple examples to demonstrate the accuracy and effectiveness of the proposed algorithm for the partial differential equation of $\mathbb{S}^2$-functions.