193 citations · 274 across the 24 of their papers we have counts for
15 papers · 1 filter
Solving Linear Systems in Bit Operations
Jonathan A. Kelner
We give a deterministic algorithm that solves a nonsingular linear system , where has nonzero entries and condition number , to any relati…
Feature Adaptation for Sparse Linear Regression
Jonathan Kelner, Frederic Koehler, Raghu Meka +1
Sparse linear regression is a central problem in high-dimensional statistics. We study the correlated random design setting, where the covariates are drawn from a multivariate Gaus…
Sampling with Barriers: Faster Mixing via Lewis Weights
Khashayar Gatmiry, Jonathan Kelner, Santosh S. Vempala
We analyze Riemannian Hamiltonian Monte Carlo (RHMC) for sampling a polytope defined by inequalities in endowed with the metric defined by the Hessian of a convex barrie…
Semi-Random Sparse Recovery in Nearly-Linear Time
Jonathan A. Kelner, Jerry Li, Allen Liu +2
Sparse recovery is one of the most fundamental and well-studied inverse problems. Standard statistical formulations of the problem are provably solved by general convex programming…
Distributional Hardness Against Preconditioned Lasso via Erasure-Robust Designs
Jonathan A. Kelner, Frederic Koehler, Raghu Meka +1
Sparse linear regression with ill-conditioned Gaussian random designs is widely believed to exhibit a statistical/computational gap, but there is surprisingly little formal evidenc…
Solving Directed Laplacian Systems in Nearly-Linear Time through Sparse LU Factorizations
Michael B. Cohen, Jonathan Kelner, Rasmus Kyng +4
We show how to solve directed Laplacian systems in nearly-linear time. Given a linear system in an Eulerian directed Laplacian with nonzero entries, we show how to…