5 papers · 2 filters
Adaptive Matrix Sparsification and Applications to Empirical Risk Minimization
Yang P. Liu, Richard Peng, Colin Tang +2
Consider the empirical risk minimization (ERM) problem, which is stated as follows. Let be compact convex sets with for $i \in [m…
Entrywise Approximate Solutions for SDDM Systems in Almost-Linear Time
Angelo Farfan, Mehrdad Ghadiri, Junzhao Yang
We present an algorithm that given any invertible symmetric diagonally dominant M-matrix (SDDM), i.e., a principal submatrix of a graph Laplacian, and a n…
Numerical Linear Algebra in Linear Space
Yiping Liu, Hoai-An Nguyen, Junzhao Yang
We present a randomized linear-space solver for general linear systems with and $\mathbf{b} \in \mathb…
Approximate Spanning Tree Counting from Uncorrelated Edge Sets
Yang P. Liu, Richard Peng, Junzhao Yang
We show an time algorithm that on a graph with edges and vertices outputs its spanning tree count up to a multiplicative factor with…
Entrywise Approximation for Matrix Inversion and Linear Systems
Mehrdad Ghadiri, Hoai-An Nguyen, Junzhao Yang
We study the bit complexity of inverting diagonally dominant matrices, which are associated with random walk quantities such as hitting times and escape probabilities. Such quantit…