193 citations · 274 across the 24 of their papers we have counts for
28 papers
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…
Lasso with Latents: Efficient Estimation, Covariate Rescaling, and Computational-Statistical Gaps
Jonathan Kelner, Frederic Koehler, Raghu Meka +1
It is well-known that the statistical performance of Lasso can suffer significantly when the covariates of interest have strong correlations. In particular, the prediction error of…
Matrix Completion in Almost-Verification Time
Jonathan A. Kelner, Jerry Li, Allen Liu +2
We give a new framework for solving the fundamental problem of low-rank matrix completion, i.e., approximating a rank- matrix (where $m…
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…