%0 Manuscript %D Submitted %T Learning Dynamical Systems and Bifurcation via Group Sparsity %A Hayden Schaeffer %A Giang Tran %A Rachel Ward %X Learning governing equations from a family of data sets which share the same physical laws but differ in bifurcation parameters is challenging. This is due, in part, to the wide range of phenomena that could be represented in the data sets as well as the range of parameter values. On the other hand, it is common to assume only a small number of candidate functions contribute to the observed dynamics. Based on these observations, we propose a group-sparse penalized method for model selection and parameter estimation for such data. We also provide convergence guarantees for our proposed numerical scheme. Various numerical experiments including the 1D logistic equation, the 3D Lorenz sampled from different bifurcation regions, and a switching system provide numerical validation for our method and suggest potential applications to applied dynamical systems. %G eng %0 Manuscript %D 2023 %T Adaptive Group Lasso Neural Network Models for Functions of Few Variables and Time-Dependent Data %A Nicholas Richardson %A Lam Si Tung Ho %A Giang Tran %X In this paper, we propose an adaptive group Lasso deep neural network for high-dimensional function approximation where input data are generated from a dynamical system and the target function depends on few active variables or few linear combinations of variables. We approximate the target function by a deep neural network and enforce an adaptive group Lasso constraint to the weights of a suitable hidden layer in order to represent the constraint on the target function. We utilize the proximal algorithm to optimize the penalized loss function. Using the non-negative property of the Bregman distance, we prove that the proposed optimization procedure achieves loss decay. Our empirical studies show that the proposed method outperforms recent state-of-the-art methods including the sparse dictionary matrix method, neural networks with or without group Lasso penalty. %B Sampling Theory, Signal Processing, and Data Analysis %G eng %U https://arxiv.org/abs/2108.10825 %0 Manuscript %D 2023 %T Generalization Bounds for Sparse Random Feature Expansions %A Abolfazl Hashemi %A Hayden Schaeffer %A Robert Shi %A Ufuk Topcu %A Giang Tran %A Rachel Ward %X Random feature methods have been successful in various machine learning tasks, are easy to compute, and come with theoretical accuracy bounds. They serve as an alternative approach to standard neural networks since they can represent similar function spaces without a costly training phase. However, for accuracy, random feature methods require more measurements than trainable parameters, limiting their use for data-scarce applications or problems in scientific machine learning. This paper introduces the sparse random feature expansion to obtain parsimonious random feature models. Specifically, we leverage ideas from compressive sensing to generate random feature expansions with theoretical guarantees even in the data-scarce setting. In particular, we provide uniform bounds on the approximation error and generalization bounds for functions in a certain class (that is dense in a reproducing kernel Hilbert space) depending on the number of samples and the distribution of features. The error bounds improve with additional structural conditions, such as coordinate sparsity, compact clusters of the spectrum, or rapid spectral decay. In particular, by introducing sparse features, i.e. features with random sparse weights, we provide improved bounds for low order functions. We show that the sparse random feature expansions outperforms shallow networks in several scientific machine learning tasks. %B Applied and Computational Harmonic Analysis %V 62 %P 310-330 %G eng %U https://www.sciencedirect.com/science/article/pii/S1063520322000653 %0 Journal Article %J Sampling Theory, Signal Processing, and Data Analysis %D 2023 %T HARFE: Hard-ridge random feature expansion %A Esha Saha %A Hayden Schaeffer %A Giang Tran %X We propose a random feature model for approximating high-dimensional sparse additive functions called the hard-ridge random feature expansion method (HARFE). This method utilizes a hard-thresholding pursuit-based algorithm applied to the sparse ridge regression (SRR) problem to approximate the coefficients with respect to the random feature matrix. The SRR formulation balances between obtaining sparse models that use fewer terms in their representation and ridge-based smoothing that tend to be robust to noise and outliers. In addition, we use a random sparse connectivity pattern in the random feature matrix to match the additive function assumption. We prove that the HARFE method is guaranteed to converge with a given error bound depending on the noise and the parameters of the sparse ridge regression model. Based on numerical results on synthetic data as well as on real datasets, the HARFE approach obtains lower (or comparable) error than other state-of-the-art algorithms. %B Sampling Theory, Signal Processing, and Data Analysis %G eng %U https://arxiv.org/abs/2202.02877 %0 Journal Article %J Bulletin of Mathematical Biology %D 2023 %T SPADE4: Sparsity and Delay Embedding Based Forecasting of Epidemics %A Esha Saha %A Lam Si Tung Ho %A Giang Tran %X

Predicting the evolution of diseases is challenging, especially when the data availability is scarce and incomplete. The most popular tools for modelling and predicting infectious disease epidemics are compartmental models. They stratify the population into compartments according to health status and model the dynamics of these compartments using dynamical systems. However, these predefined systems may not capture the true dynamics of the epidemic due to the complexity of the disease transmission and human interactions. In order to overcome this drawback, we propose Sparsity and Delay Embedding based Forecasting (SPADE4) for predicting epidemics. SPADE4 predicts the future trajectory of an observable variable without the knowledge of the other variables or the underlying system. We use random features model with sparse regression to handle the data scarcity issue and employ Takens’ delay embedding theorem to capture the nature of the underlying system from the observed variable. We show that our approach outperforms compartmental models when applied to both simulated and real data.

%B Bulletin of Mathematical Biology %G eng %U https://link.springer.com/article/10.1007/s11538-023-01174-z %0 Journal Article %J Communications on Applied Mathematics and Computation %D 2023 %T SRMD: Sparse random mode decomposition %A Nicholas Richardson %A Hayden Schaeffer %A Giang Tran %X

Signal decomposition and multiscale signal analysis provide many useful tools for time-frequency analysis. We proposed a random feature method for analyzing time-series data by constructing a sparse approximation to the spectrogram. The randomization is both in the time window locations and the frequency sampling, which lowers the overall sampling and computational cost. The sparsification of the spectrogram leads to a sharp separation between time-frequency clusters which makes it easier to identify intrinsic modes, and thus leads to a new data-driven mode decomposition. The applications include signal representation, outlier removal, and mode decomposition. On benchmark tests, we show that our approach outperforms other state-of-the-art decomposition methods.

 
%B Communications on Applied Mathematics and Computation %P 1-28 %G eng %U https://link.springer.com/article/10.1007/s42967-023-00273-x %0 Journal Article %J Multiscale Modeling & Simulation %D 2020 %T Extracting Structured Dynamical Systems using Sparse Optimization with very Few Samples %A Hayden Schaeffer %A Giang Tran %A Rachel Ward %A Linan Zhang %X

Learning governing equations allows for deeper understanding of the structure and dynamics of data. We present a random sampling method for learning structured dynamical systems from under-sampled and possibly noisy state-space measurements. The learning problem takes the form of a sparse least-squares fitting over a large set of candidate functions. Based on a Bernstein-like inequality for partly dependent random variables, we provide theoretical guarantees on the recovery rate of the sparse coefficients and the identification of the candidate functions for the corresponding problem. Computational results are demonstrated on datasets generated by the Lorenz 96 equation, the viscous Burgers' equation, and the two-component reaction-diffusion equations (which is challenging due to parameter sensitives in the model). This formulation has several advantages including ease of use, theoretical guarantees of success, and computational efficiency with respect to ambient dimension and number of candidate functions.

%B Multiscale Modeling & Simulation %V 18 %G eng %N 4 %0 Journal Article %J Journal of Approximation Theory %D 2020 %T Recovery Guarantees for Polynomial Approximation from Dependent Data with Outliers %A Lam S.T. Ho %A Hayden Schaeffer %A Giang Tran %A Rachel Ward %X Learning non-linear systems from noisy, limited, and/or dependent data is an important task across various scientific fields including statistics, engineering, computer science, mathematics, and many more. In general, this learning task is ill-posed; however, additional information about data structure or behavior of the unknown function can make the task well-posed. In this work, we study the problem of learning nonlinear functions from corrupted and dependent data. The learning problem is recast as a sparse robust linear regression problem where we incorporate both the unknown coefficients and the corruptions in a basis pursuit framework. The main contribution of our paper is to provide a reconstruction guarantee for the associated $\ell_1$-optimization problem where the sampling matrix is formed from dependent data. Specifically, we prove that the sampling matrix satisfies the null space property and the stable null space property, provided that the data is compact and satisfies a suitable concentration inequality. We show that our recovery results are applicable to various types of dependent data such as exponentially strongly $\alpha$-mixing data, geometrically $\mathcal{C}$-mixing data, and uniformly ergodic Markov chain. Our theoretical results are verified via several numerical simulations. %B Journal of Approximation Theory %V 259 %G eng %U https://www.sciencedirect.com/science/article/abs/pii/S0021904520301088 %0 Journal Article %J SIAM Journal on Applied Mathematics %D 2018 %T Extracting Sparse High-Dimensional Dynamics from Limited Data %A Hayden Schaeffer %A Giang Tran %A Rachel Ward %X Extracting governing equations from dynamic data is an essential task in model selection and parameter estimation. The form of the governing equation is rarely known a priori; however, based on the sparsity-of-effect principle one may assume that the number of candidate functions needed to represent the dynamics is very small. In this work, we leverage the sparse structure of the governing equations along with recent results from random sampling theory to develop methods for selecting dynamical systems from under-sampled data. In particular, we detail three sampling strategies that lead to the exact recovery of first-order dynamical systems when we are given fewer samples than unknowns. The first method makes no assumptions on the behavior of the data, and requires a certain number of random initial samples. The second method utilizes the structure of the governing equation to limit the number of random initializations needed. The third method leverages chaotic behavior in the data to construct a nearly deterministic sampling strategy. Using results from compressive sensing, we show that the strategies lead to exact recovery, which is stable to the sparse structure of the governing equations and robust to noise in the estimation of the velocity. Computational results validate each of the sampling strategies and highlight potential applications. %B SIAM Journal on Applied Mathematics %8 2018 %G eng %0 Journal Article %J Multiscale Modeling & Simulation %D 2017 %T Exact Recovery of Chaotic Systems from Highly Corrupted Data %A Giang Tran %A Rachel Ward %X

Learning the governing equations in dynamical systems from time-varying measurements is of great interest across different scientific fields. This task becomes prohibitive when such data is, moreover, highly corrupted, for example, due to the recording mechanism failing over unknown intervals of time. When the underlying system exhibits chaotic behavior, such as sensitivity to initial conditions, it is crucial to recover the governing equations with high precision. In this work, we consider continuous time dynamical systems $\dot{x} = f(x)$ where each component of $f: \mathbb{R}^{d} \rightarrow \mathbb{R}^d$ is a multivariate polynomial of maximal degree $p$; we aim to identify $f$ exactly from possibly highly corrupted measurements $x(t_1), x(t_2), \dots, x(t_m)$. As our main theoretical result, we show that if the system is sufficiently ergodic that this data satisfies a strong central limit theorem (as is known to hold for chaotic Lorenz systems), then the governing equations $f$ can be exactly recovered as the solution to an $\ell_1$ minimization problem---even if a large percentage of the data is corrupted by outliers. Numerically, we apply the alternating minimization method to solve the corresponding constrained optimization problem. Through several examples of three-dimensional chaotic systems and higher-dimensional hyperchaotic systems, we illustrate the power, generality, and efficiency of the algorithm for recovering governing equations from noisy and highly corrupted measurement data.

%B Multiscale Modeling & Simulation %V 15 %P 1108-1129 %G eng %N 3 %0 Journal Article %J ACS Nano %D 2015 %T Defect-Tolerant Aligned Dipoles within Two-Dimensional Plastic Lattices %A John C Thomas %A Jeffrey J Schwartz %A J Nathan Hohman %A Shelley A Claridge %A Harsharn S Auluck %A Andrew C Serino %A Alexander M Spokoyny %A Giang Tran %A Kevin F Kelly %A Chad A Mirkin %A Jerome Gilles %A Stanley J Osher %A Paul S Weiss %X Carboranethiol molecules self-assemble into upright molecular monolayers on Au{111} with aligned dipoles in two dimensions. The positions and offsets of each molecule’s geometric apex and local dipole moment are measured and correlated with sub-Ångström precision. Juxtaposing simultaneously acquired images, we observe monodirectional offsets between the molecular apexes and dipole extrema. We determine dipole orientations using efficient new image analysis techniques and find aligned dipoles to be highly defect tolerant, crossing molecular domain boundaries and substrate step edges. The alignment observed, consistent with Monte Carlo simulations, forms through favorable intermolecular dipole–dipole interactions. %B ACS Nano %V 9 %P 4734-4742 %G eng %N 5 %0 Journal Article %J IEEE Transactions on Medical Imaging %D 2015 %T Fiber Orientation and Compartment Parameter Estimation from Multi-Shell Diffusion Imaging %A Giang Tran %A Yonggang Shi %X

Diffusion MRI offers the unique opportunity of assessing the structural connections of human brains in vivo. With the advance of diffusion MRI technology, multi-shell imaging methods are becoming increasingly practical for large scale studies and clinical application. In this work, we propose a novel method for the analysis of multi-shell diffusion imaging data by incorporating compartment models into a spherical deconvolution framework for fiber orientation distribution (FOD) reconstruction. For numerical implementation, we develop an adaptively constrained energy minimization approach to efficiently compute the solution. On simulated and real data from Human Connectome Project (HCP), we show that our method not only reconstructs sharp and clean FODs for the modeling of fiber crossings, but also generates reliable estimation of compartment parameters with great potential for clinical research of neurological diseases. In comparisons with publicly available DSI-Studio and BEDPOSTX of FSL, we demonstrate that our method reconstructs sharper FODs with more precise estimation of fiber directions. By applying probabilistic tractography to the FODs computed by our method, we show that more complete reconstruction of the corpus callosum bundle can be achieved. On a clinical, two-shell diffusion imaging data, we also demonstrate the feasibility of our method in analyzing white matter lesions.

%B IEEE Transactions on Medical Imaging %V 34 %P 2320-2332 %G eng %N 11 %0 Book Section %B Research in Shape Modeling %D 2015 %T Identifying Perceptually Salient Features on 2D Shapes %A Lisa J. Larsson %A Géraldine Morin %A Antoine Begault %A Raphaëlle Chaine %A Jeannine Abiva %A Evelyne Hubert %A Monica Hurdal %A Mao Li %A Beatriz Paniagua %A Giang Tran %A Marie-Paule Cani %X Maintaining the local style and scale of 2D shape features during deformation, such as when elongating, compressing, or bending a shape, is essential for interactive shape editing. To achieve this, a necessary first step is to develop a robust classification method able to detect salient shape features, if possible in a hierarchical manner. Our aim is to overcome the limitations of existing techniques, which are not always able to detect what a user immediately identifies as a shape feature. Therefore, we first conduct a user study enabling us to learn how shape features are perceived. We then propose and compare several algorithms, all based on the medial axis transform or similar skeletal representations, to identify relevant shape features from this perceptual viewpoint. We discuss the results of each algorithm and compare them with those of the user study, leading to a practical solution for computing hierarchies of salient features on 2D shapes. %B Research in Shape Modeling %I Springer, Cham %P 129-153 %G eng %0 Journal Article %J SIAM Journal on Applied Mathematics %D 2015 %T An L1 Penalty Method for General Obstacle Problems %A Giang Tran %A Hayden Schaeffer %A William Feldman %A Stanley Osher %X

We construct an efficient numerical scheme for solving obstacle problems in divergence form. The numerical method is based on a reformulation of the obstacle in terms of an $L^1$-like penalty on the variational problem. The reformulation is an exact regularizer in the sense that for a large (but finite) penalty parameter, we recover the exact solution. Our formulation is applied to classical elliptic obstacle problems as well as some related free boundary problems, for example, the two-phase membrane problem and the Hele--Shaw model. One advantage of the proposed method is that the free boundary inherent in the obstacle problem arises naturally in our energy minimization without any need for problem specific or complicated discretization. Also, our scheme also works for nonlinear variational inequalities arising from convex minimization problems.

 

%B SIAM Journal on Applied Mathematics %V 75 %P 1424-1444 %G eng %N 4 %0 Journal Article %J SIAM Journal on Imaging Sciences %D 2015 %T Non-local Retinex - A Unifying Framework and Beyond %A Dominique Zosso %A Giang Tran %A Stanley Osher %X

In this paper, we provide a short review of Retinex and then present a unifying framework. The fundamental assumption of all Retinex models is that the observed image is a multiplication between the illumination and the true underlying reflectance of the object. Starting from Morel's 2010 PDE model, where illumination is supposed to vary smoothly and where the reflectance is thus recovered from a hard-thresholded Laplacian of the observed image in a Poisson equation, we define our unifying Retinex model in two similar, but more general, steps. We reinterpret the gradient thresholding model as variational models with sparsity constraints. First, we look for a filtered gradient that is the solution of an optimization problem consisting of two terms: a sparsity prior of the reflectance and a fidelity prior of the reflectance gradient to the observed image gradient. Second, since this filtered gradient almost certainly is not a consistent image gradient, we then fit an actual reflectance gradient to it, subject to further sparsity and fidelity priors. This generalized formulation allows making connections with other variational or kernel-based Retinex implementations. We provide simple algorithms for the optimization problems resulting from our framework. In particular, in the quadratic case, we can link our model to a plausible neural mechanism through Wilson--Cowan equations. Beyond unifying existing models, we derive entirely novel Retinex flavors by using more interesting non-local versions for the sparsity and fidelity priors. Eventually, we define within a single framework new Retinex applications to shadow detection and removal, nonuniformity correction, cartoon-texture decomposition, as well as color and hyperspectral image enhancement.

 

%B SIAM Journal on Imaging Sciences %V 8 %P 787–826 %G eng %N 2 %0 Journal Article %J Communications in Mathematical Sciences %D 2015 %T PDEs with Compressed Solutions %A Russel E Caflisch %A Stanley J Osher %A Hayden Schaeffer %A Giang Tran %X

Sparsity plays a central role in recent developments in signal processing, linear algebra, statistics, optimization, and other fields. In these developments, sparsity is promoted through the addition of an L1 norm (or related quantity) as a constraint or penalty in a variational principle. We apply this approach to partial differential equations that come from a variational quantity, either by minimization (to obtain an elliptic PDE) or by gradient flow (to obtain a parabolic PDE). Also, we show that some PDEs can be rewritten in an L1 form, such as the divisible sandpile problem and signum-Gordon. Addition of an L1 term in the variational principle leads to a modified PDE where a subgradient term appears. It is known that modified PDEs of this form will often have solutions with compact support, which corresponds to the discrete solution being sparse. We show that this is advantageous numerically through the use of efficient algorithms for solving L1 based problems.

%B Communications in Mathematical Sciences %V 13 %P 2155--2176 %G eng %N 8 %0 Journal Article %J SIAM Journal on Imaging Sciences %D 2014 %T 2D Empirical Transforms. Wavelets, Ridgelets, and Curvelets Revisited %A Jerome Gilles %A Giang Tran %A Stanley Osher %X A recently developed approach, called “empirical wavelet transform,” aims to build one-dimensional (1D) adaptive wavelet frames accordingly to the analyzed signal. In this paper, we present several extensions of this approach to two-dimensional (2D) signals (images). We revisit some well-known transforms (tensor wavelets, Littlewood--Paley wavelets, ridgelets, and curvelets) and show that it is possible to build their empirical counterparts. We prove that such constructions lead to different adaptive frames which show some promising properties for image analysis and processing. %B SIAM Journal on Imaging Sciences %V 7 %P 157-186 %G eng %N 1 %0 Journal Article %J IEEE Transactions on Medical Imaging %D 2014 %T Fast Local Trust Region Technique for Diffusion Tensor Registration Using Exact Reorientation and Regularization %A Junning Li %A Yonggang Shi %A Giang Tran %A Ivo Dinov %A Danny JJ Wang %A Arthur Toga %X Diffusion tensor imaging is widely used in brain connectivity research. As more and more studies recruit large numbers of subjects, it is important to design registration methods which are not only theoretically rigorous, but also computationally efficient. However, the requirement of reorienting diffusion tensors complicates and considerably slows down registration procedures, due to the correlated impacts of registration forces at adjacent voxel locations. Based on the diffeomorphic Demons algorithm (Vercauteren , 2009), we propose a fast local trust region algorithm for handling inseparable registration forces for quadratic energy functions. The method guarantees that, at any time and at any voxel location, the velocity is always within its local trust region. This local regularization allows efficient calculation of the transformation update with numeric integration instead of completely solving a large linear system at every iteration. It is able to incorporate exact reorientation and regularization into the velocity optimization, and preserve the linear complexity of the diffeomorphic Demons algorithm. In an experiment with 84 diffusion tensor images involving both pair-wise and group-wise registrations, the proposed algorithm achieves better registration in comparison with other methods solving large linear systems (Yeo , 2009). At the same time, this algorithm reduces the computation time and memory demand tenfold. %B IEEE Transactions on Medical Imaging %V 33 %P 1005 - 1022 %G eng %N 5 %0 Conference Paper %B International Conference on Medical Image Computing and Computer-Assisted Intervention (MICCAI) %D 2013 %T Adaptively Constrained Convex Optimization for Accurate Fiber Orientation Estimation with High Order Spherical Harmonics %A Giang Tran %A Yonggang Shi %X

Diffusion imaging data from the Human Connectome Project (HCP) provides a great opportunity to map the whole brain white matter connectivity to unprecedented resolution in vivo. In this paper we develop a novel method for accurately reconstruct fiber orientation distribution from cutting-edge diffusion data by solving the spherical deconvolution problem as a constrained convex optimization problem. With a set of adaptively selected constraints, our method allows the use of high order spherical harmonics to reliably resolve crossing fibers with small separation angles. In our experiments, we demonstrate on simulated data that our algorithm outperforms a popular spherical deconvolution method in resolving fiber crossings. We also successfully applied our method to the multi-shell and diffusion spectrum imaging (DSI) data from HCP to demonstrate its ability in using state-of-the-art diffusion data to study complicated fiber structures.

%B International Conference on Medical Image Computing and Computer-Assisted Intervention (MICCAI) %I Springer, Berlin, Heidelberg %C MICCAI 2013, %P 485-492 %G eng %0 Conference Paper %B Computational Imaging XI %D 2013 %T A Unifying Retinex Model Based on Non-Local Differential Operators %A Dominique Zosso %A Giang Tran %A Stanley Osher %X In this paper, we present a unifying framework for retinex that is able to reproduce many of the existing retinex implementations within a single model. The fundamental assumption, as shared with many retinex models, is that the observed image is a multiplication between the illumination and the true underlying reflectance of the object. Starting from Morel’s 2010 PDE model for retinex, where illumination is supposed to vary smoothly and where the reflectance is thus recovered from a hard-thresholded Laplacian of the observed image in a Poisson equation, we define our retinex model in similar but more general two steps. First, look for a filtered gradient that is the solution of an optimization problem consisting of two terms: The first term is a sparsity prior of the reflectance, such as the TV or H1 norm, while the second term is a quadratic fidelity prior of the reflectance gradient with respect to the observed image gradients. In a second step, since this filtered gradient almost certainly is not a consistent image gradient, we then look for a reflectance whose actual gradient comes close. Beyond unifying existing models, we are able to derive entirely novel retinex formulations by using more interesting non-local versions for the sparsity and fidelity prior. Hence we define within a single framework new retinex instances particularly suited for texture-preserving shadow removal, cartoon-texture decomposition, color and hyperspectral image enhancement. %B Computational Imaging XI %I International Society for Optics and Photonics %V 8657 %G eng %0 Conference Paper %B International Conference on Medical Image Computing and Computer-Assisted Intervention (MICCAI) %D 2012 %T Fast Diffusion Tensor Registration with Exact Reorientation and Regularization %A Junning Li %A Yonggang Shi %A Giang Tran %A Ivo Dinov %A Danny JJ Wang %A Arthur W Toga %X Diffusion tensor imaging is widely used in brain connectivity study. As more and more group studies recruit a large number of subjects, it is important to design registration methods that are not only theoretically rigorous, but also computationally efficient, for processing large data sets. However, the requirement of reorienting diffusion tensors complicates and slows down the registration, especially for those methods whose scalar-image versions have linear complexity, for example, the Demons algorithm. In this paper, we propose an extension of the Demons algorithm that incorporates exact reorientation and regularization into the calculation of deforming velocity, yet preserving its linear complexity. This method restores the computational efficiency of the Demons algorithm to diffusion images, but does not sacrifice registration goodness. In our experiments, the new algorithm achieved state-of-art performance at a ten-fold decrease of computational time. %B International Conference on Medical Image Computing and Computer-Assisted Intervention (MICCAI) %I Springer, Berlin, Heidelberg %P 138-145 %G eng