6 papers · 1 filter
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…
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…
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 wi…
Entrywise Approximate Laplacian Solving
Jingbang Chen, Mehrdad Ghadiri, Hoai-An Nguyen +2
We study the escape probability problem in random walks over graphs. Given vertices, and , the problem asks for the probability that a random walk starting at will hi…