Skip to main content
Open Access Publications from the University of California


UCLA Electronic Theses and Dissertations bannerUCLA

Sparsity-Inducing Methods in Imaging Sciences and Partial Differential Equations

  • Author(s): Tran, Giang Thi Tra
  • Advisor(s): Osher, Stanley
  • et al.

Sparsity has played a central role in many fields of applied mathematics such as signal processing, image processing, compressed sensing, and optimization. Theoretically, sparse solutions are of interested in these fields because they can be recovered exactly from ill-posed inverse problems. Numerically, methods for computing sparse solutions have fast and efficient implementations, making them extremely practical. In terms of modeling, sparsity is promoted through the addition of an $L^1$ norm (or related quantity) as a constraint or penalty in a variational model. This methodology is also related to various properties of solutions of partial differential equations (PDEs) including compact support sets for free boundary problems and sparse representation of the solution space. Recently, sparsity-inducing methods used in image processing and compressed sensing have been applied to computational PDEs and applied harmonic analysis.

Part I of the thesis focuses on the construction of efficient numerical schemes for PDEs with sparse structures. From the early theoretical work on variational inequalities, it was showed that PDEs with $L^1$ subdifferential terms have unique solutions with compact supports which can be considered to be sparse in the discrete sense. We considered an elliptic PDE derived from a variational principle or a parabolic PDE associated with the gradient flow of a convex functional. In order to compute the solutions, fast computational schemes were introduced to solve the resulting minimization problem. Those methods can handle the multivalued nature of the sub-gradient $\partial \|u\|_{L^1}$, which involve the proximal operator of the $L^1$ term. Although these methods are popular in imaging and data science, their applications in PDEs are limited.

The $L^1$-based methodology was also introduced to elliptic obstacle problems and related free boundary problems such as Hele-Shaw flow, two-phase membrane, and divisible sandpile. Our numerical methods are based on a reformulation of those PDEs in terms of $L^1$-like penalties on the associated variational problems. One advantage of the proposed methods is that the free boundary inherent in the obstacle problem arises naturally in the energy minimization without any need for problem specific or complicated discretization. Moreover, the numerical solution can be computed using fast and simple algorithms.

Part II of the thesis focuses on data decomposition methods to extract important features or recover the intrinsic properties from the original data. From the variational approaches, a unifying retinex framework was developed to decompose an image into two components with certain sparsity and fidelity priors. The unified formulation connects many retinex implementations into one model. Moreover, new retinex applications were introduced within a single framework which includes shadow detection, cartoon-texture decomposition, nonuniform illumination correction and color contrast enhancement.

Main Content
Current View