Matrix Completion With Cross-Concentrated Sampling: Bridging Uniform Sampling and CUR Sampling.

While uniform sampling has been widely studied in the matrix completion literature, CUR sampling approximates a low-rank matrix via row and column samples. Unfortunately, both sampling models lack flexibility for various circumstances in real-world applications. In this work, we propose a novel and easy-to-implement sampling strategy, coined Cross-Concentrated Sampling (CCS). By bridging uniform sampling and CUR sampling, CCS provides extra flexibility that can potentially save sampling costs in applications. In addition, we also provide a sufficient condition for CCS-based matrix completion. Moreover, we propose a highly efficient non-convex algorithm, termed Iterative CUR Completion (ICURC), for the proposed CCS model. Numerical experiments verify the empirical advantages of CCS and ICURC against uniform sampling and its baseline algorithms, on both synthetic and real-world datasets.

The Manifold Scattering Transform for High-Dimensional Point Cloud Data.

The manifold scattering transform is a deep feature extractor for data defined on a Riemannian manifold. It is one of the first examples of extending convolutional neural network-like operators to general manifolds. The initial work on this model focused primarily on its theoretical stability and invariance properties but did not provide methods for its numerical implementation except in the case of two-dimensional surfaces with predefined meshes. In this work, we present practical schemes, based on the theory of diffusion maps, for implementing the manifold scattering transform to datasets arising in naturalistic systems, such as single cell genetics, where the data is a high-dimensional point cloud modeled as lying on a low-dimensional manifold. We show that our methods are effective for signal classification and manifold classification tasks.

HOSVD-Based Algorithm for Weighted Tensor Completion.

Matrix completion, the problem of completing missing entries in a data matrix with low-dimensional structure (such as rank), has seen many fruitful approaches and analyses. Tensor completion is the tensor analog that attempts to impute missing tensor entries from similar low-rank type assumptions. In this paper, we study the tensor completion problem when the sampling pattern is deterministic and possibly non-uniform. We first propose an efficient weighted Higher Order Singular Value Decomposition (HOSVD) algorithm for the recovery of the underlying low-rank tensor from noisy observations and then derive the error bounds under a properly weighted metric. Additionally, the efficiency and accuracy of our algorithm are both tested using synthetic and real datasets in numerical simulations.

Analysis of fast structured dictionary learning.

Sparsity-based models and techniques have been exploited in many signal processing and imaging applications. Data-driven methods based on dictionary and sparsifying transform learning enable learning rich image features from data and can outperform analytical models. In particular, alternating optimization algorithms have been popular for learning such models. In this work, we focus on alternating minimization for a specific structured unitary sparsifying operator learning problem and provide a convergence analysis. While the algorithm converges to the critical points of the problem generally, our analysis establishes under mild assumptions, the local linear convergence of the algorithm to the underlying sparsifying model of the data. Analysis and numerical simulations show that our assumptions hold for standard probabilistic data models. In practice, the algorithm is robust to initialization.

Antibiotic Treatment Response in Chronic Lyme Disease: Why Do Some Patients Improve While Others Do Not?

There is considerable uncertainty regarding treatment of Lyme disease patients who do not respond fully to initial short-term antibiotic therapy. Choosing the best treatment approach and duration remains challenging because treatment response among these patients varies: some patients improve with treatment while others do not. A previous study examined treatment response variation in a sample of over 3500 patients enrolled in the MyLymeData patient registry developed by LymeDisease.org (San Ramon, CA, USA). That study used a validated Global Rating of Change (GROC) scale to identify three treatment response subgroups among Lyme disease patients who remained ill: nonresponders, low responders, and high responders. The present study first characterizes the health status, symptom severity, and percentage of treatment response across these three patient subgroups together with a fourth subgroup, patients who identify as well. We then employed machine learning techniques across these subgroups to determine features most closely associated with improved patient outcomes, and we used traditional statistical techniques to examine how these features relate to treatment response of the four groups. High treatment response was most closely associated with (1) the use of antibiotics or a combination of antibiotics and alternative treatments, (2) longer duration of treatment, and (3) oversight by a clinician whose practice focused on the treatment of tick-borne diseases.

Fast Hyperspectral Diffuse Optical Imaging Method with Joint Sparsity.

Diffuse optical tomography (DOT) is an important functional imaging modality in clinical diagnosis and treatment. As the number of wavelengths in the acquired DOT data grows, it becomes very challenging to reconstruct diffusion and absorption coefficients of tissue, i.e., a DOT image. In this paper, we consider the hyperspectral DOT (hyDOT) inverse problem as a multiple-measurement vector (MMV) problem by exploiting the joint sparsity of the images to be reconstructed. Then we propose a fast stochastic greedy algorithm based on the MMV stochastic gradient matching pursuit (MStoGradMP) and the mini-batching technique. Numerical results show that the proposed algorithm can achieve higher reconstruction accuracy with significantly reduced running time than the related gradient descent method with sparsity regularization.

Near-optimal compressed sensing guarantees for total variation minimization.

Consider the problem of reconstructing a multidimensional signal from an underdetermined set of measurements, as in the setting of compressed sensing. Without any additional assumptions, this problem is ill-posed. However, for signals such as natural images or movies, the minimal total variation estimate consistent with the measurements often produces a good approximation to the underlying signal, even if the number of measurements is far smaller than the ambient dimensionality. This paper extends recent reconstruction guarantees for two-dimensional images [Formula: see text] to signals [Formula: see text] of arbitrary dimension d ≥ 2 and to isotropic total variation problems. In this paper, we show that a multidimensional signal [Formula: see text] can be reconstructed from O(s dlog(N(d))) linear measurements [Formula: see text] using total variation minimization to a factor of the best s -term approximation of its gradient. The reconstruction guarantees we provide are necessarily optimal up to polynomial factors in the spatial dimension d.