More Like this

1. Accumulations of Projections—A Unified Framework for Random Sketches in Kernel Ridge Regression

   Chen, Yifan ; Yang, Yun. ( January 2021 , Proceedings of Machine Learning Research)

   null (Ed.)

   Building a sketch of an n-by-n empirical kernel matrix is a common approach to accelerate the computation of many kernel methods. In this paper, we propose a unified framework of constructing sketching methods in kernel ridge regression (KRR), which views the sketching matrix S as an accumulation of m rescaled sub-sampling matrices with independent columns. Our framework incorporates two commonly used sketching methods, sub-sampling sketches (known as the Nyström method) and sub-Gaussian sketches, as special cases with m=1 and m=infinity respectively. Under the new framework, we provide a unified error analysis of sketching approximation and show that our accumulation scheme improves the low accuracy of sub-sampling sketches when certain incoherence characteristic is high, and accelerates the more accurate but computationally heavier sub-Gaussian sketches. By optimally choosing the number m of accumulations, we show that a best trade-off between computational efficiency and statistical accuracy can be achieved. In practice, the sketching method can be as efficiently implemented as the sub-sampling sketches, as only minor extra matrix additions are needed. Our empirical evaluations also demonstrate that the proposed method may attain the accuracy close to sub-Gaussian sketches, while is as efficient as sub-sampling-based sketches. 

   more » « less
2. Determinant Maximization via Matroid Intersection Algorithms

   Brown, A ; Laddha, A. ; Pittu, M. ; Singh, M. ; Tetali, P. ( October 2022 , Annual Symposium on Foundations of Computer Science)

   Determinant maximization problem gives a general framework that models problems arising in as diverse fields as statistics [Puk06], convex geometry [Kha96], fair allocations [AGSS16], combinatorics [AGV18], spectral graph theory [NST19a], network design, and random processes [KT12]. In an instance of a determinant maximization problem, we are given a collection of vectors U = {v1, . . . , vn} ⊂ Rd , and a goal is to pick a subset S ⊆ U of given vectors to maximize the determinant of the matrix ∑i∈S vivi^T. Often, the set S of picked vectors must satisfy additional combinatorial constraints such as cardinality constraint (|S| ≤ k) or matroid constraint (S is a basis of a matroid defined on the vectors). In this paper, we give a polynomial-time deterministic algorithm that returns a r O(r)-approximation for any matroid of rank r ≤ d. This improves previous results that give e O(r^2)-approximation algorithms relying on e^O(r)-approximate estimation algorithms [NS16, AG17,AGV18, MNST20] for any r ≤ d. All previous results use convex relaxations and their relationship to stable polynomials and strongly log-concave polynomials. In contrast, our algorithm builds on combinatorial algorithms for matroid intersection, which iteratively improve any solution by finding an alternating negative cycle in the exchange graph defined by the matroids. While the det(.) function is not linear, we show that taking appropriate linear approximations at each iteration suffice to give the improved approximation algorithm. 

   more » « less
3. Coil sketching for computationally efficient MR iterative reconstruction

   https://doi.org/10.1002/mrm.29883  

   Oscanoa, Julio A. ; Ong, Frank ; Iyer, Siddharth S. ; Li, Zhitao ; Sandino, Christopher M. ; Ozturkler, Batu ; Ennis, Daniel B. ; Pilanci, Mert ; Vasanawala, Shreyas S. ( October 2023 , Magnetic Resonance in Medicine)

   Parallel imaging and compressed sensing reconstructions of large MRI datasets often have a prohibitive computational cost that bottlenecks clinical deployment, especially for three‐dimensional (3D) non‐Cartesian acquisitions. One common approach is to reduce the number of coil channels actively used during reconstruction as in coil compression. While effective for Cartesian imaging, coil compression inherently loses signal energy, producing shading artifacts that compromise image quality for 3D non‐Cartesian imaging. We propose coil sketching, a general and versatile method for computationally‐efficient iterative MR image reconstruction.

   We based our method on randomized sketching algorithms, a type of large‐scale optimization algorithms well established in the fields of machine learning and big data analysis. We adapt the sketching theory to the MRI reconstruction problem via a structured sketching matrix that, similar to coil compression, considers high‐energy virtual coils obtained from principal component analysis. But, unlike coil compression, it also considers random linear combinations of the remaining low‐energy coils, effectively leveraging information from all coils.

   First, we performed ablation experiments to validate the sketching matrix design on both Cartesian and non‐Cartesian datasets. The resulting design yielded both improved computatioanal efficiency and preserved signal‐to‐noise ratio (SNR) as measured by the inverse g‐factor. Then, we verified the efficacy of our approach on high‐dimensional non‐Cartesian 3D cones datasets, where coil sketching yielded up to three‐fold faster reconstructions with equivalent image quality.

   Coil sketching is a general and versatile reconstruction framework for computationally fast and memory‐efficient reconstruction.

    

   more » « less
4. Bridging Imaging, Genetics, and Diagnosis in a Coupled Low-Dimensional Framework

   Sayan Ghosal, Qiang Chen ( October 2019 , Medical Image Computing and Computer Assisted Intervention)

   We propose a joint dictionary learning framework that couples imaging and genetics data in a low dimensional subspace as guided by clinical diagnosis. We use a graph regularization penalty to simultaneously capture inter-regional brain interactions and identify the representative set anatomical basis vectors that span the low dimensional space. We further employ group sparsity to find the representative set of genetic basis vectors that span the same latent space. Finally, the latent projection is used to classify patients versus controls. We have evaluated our model on two task fMRI paradigms and single nucleotide polymorphism (SNP) data from schizophrenic patients and matched neurotypical controls. We employ a ten fold cross validation technique to show the predictive power of our model. We compare our model with canonical correlation analysis of imaging and genetics data and random forest classification. Our approach shows better prediction accuracy on both task datasets. Moreover, the implicated brain regions and genetic variants underlie the well documented deficits in schizophrenia. 

   more » « less
5. Mapper Interactive: A Scalable, Extendable, and Interactive Toolbox for the Visual Exploration of High-Dimensional Data

   https://doi.org/10.1109/PacificVis52677.2021.00021  

   Zhou, Youjia ; Chalapathi, Nithin ; Rathore, Archit ; Zhao, Yaodong ; Wang, Bei ( April 2021 , IEEE 14th Pacific Visualization Symposium (PacificVis))

   The mapper algorithm is a popular tool from topological data analysis for extracting topological summaries of high-dimensional datasets. In this paper, we present Mapper Interactive, a web-based framework for the interactive analysis and visualization of high-dimensional point cloud data. It implements the mapper algorithm in an interactive, scalable, and easily extendable way, thus supporting practical data analysis. In particular, its command-line API can compute mapper graphs for 1 million points of 256 dimensions in about 3 minutes (4 times faster than the vanilla implementation). Its visual interface allows on-the-fly computation and manipulation of the mapper graph based on user-specified parameters and supports the addition of new analysis modules with a few lines of code. Mapper Interactive makes the mapper algorithm accessible to nonspecialists and accelerates topological analytics workflows. 

   more » « less