Randomized Numerical Linear Algebra and Applications 2018
2018-09-24..2018-09-27
Berkeley, United States
[Information Theory, Learning and Big Data (Simons Institute, 2015), Optimization and Algorithm Design 2023, Optimization, Statistics and Uncertainty, Workshop on Succinct Data Representations and Applications (Simons Institute Big Data 2013), Learning, Algorithm Design and Beyond Worst-Case Analysis, Semidefinite Optimization, Approximation and Applications 2014]
| title | author | length |
|---|---|---|
| Randomized Numerical Linear Algebra: Overview | Petros Drineas | 32m |
Survey of methods that turn giant matrices into small matrix sketches by sampling columns, rows or entries or by random projections and then run standard… | ||
| Randomized Least Squares Regression: Combining Model- and Algorithm-Induced Uncertainties | Ilse Ipsen | 24m |
Derives exact equalities for the combined estimator bias and variance when row-sketching a Gaussian linear model, using pseudo-inverses, conditional… | ||
| Advanced Techniques for Low-Rank Matrix Approximation | Ming Gu | 32m |
Presents spectral-revealing QR as a concrete alternative to rank-revealing QR, proves constant-factor bounds for truncated QR and flip-flop (QLP) improving… | ||
| Recent Advances in Positive Semidefinite Matrix Approximation | Cameron Musco | 29m |
Shows how PSD structure yields sublinear-time low-rank approximation: a 1+ε Frobenius-error factorization is possible without reading all N^2 entries by… | ||
| Reconstructing Continuous Signals via Leverage Score Sampling | Chris Musco | 32m |
Gives a tight, computable sample-complexity for recovering continuous signals under any Fourier prior and an efficient algorithm that actually constructs the… | ||
| Asympirical Analysis: Theory Informs Practice | Ping Ma | 26m |
Proposes asympirical analysis: use asymptotic formulas to extrapolate tuning parameters found on a small randomized subsample back to the full-sample… | ||
| How Randomized Analysis Can Help Us Do “Data Science:” Examples in Deep Learning and Graph Analysis | Fred Roosta | 32m |
Randomized analysis shows that with common random initializations, deep feedforward nets map different inputs to nearly the same representation: the angle… | ||
| Why Deep Learning Works: Implicit Self-Regularization in Deep Neural Networks | Michael Mahoney | 38m |
Claim: deep nets develop implicit self-regularization visible in the singular-value spectra of layer weight matrices. Empirical toolset uses heavy-tailed… | ||
| Stochastic Quasi-Gradient Methods: Variance Reduction via Jacobian Sketching | Peter Richtarik | 33m |
Introduces JacSketch, a variance-reduced stochastic optimizer that maintains cheap, sketched estimates of the full Jacobian and uses a sketch-and-project… | ||
| Randomized Riemannian Preconditioning for Quadratically Constrained Problems | Haim Avron | 31m |
Randomized sketching builds an approximate Riemannian metric for CCA by replacing Sigma_xx and Sigma_yy with cheaply formed MX and MY (via subspace embedding… | ||
| Convergence Theory for Iterative Eigensolvers | Mark Embree | 35m |
Projection methods for computing m eigenvalues rely on two explicit constants (a starting-vector orientation c1 and an eigenvector‑conditioning c2) times a… | ||
| Randomized Algorithms for Computing Full Matrix Factorizations | Gunnar Martinsson | 35m |
Randomized projections produce a blocked UTV-style factorization that reveals rank while spending almost all work in matrix–matrix multiplies; a single pass… | ||
| Applying Randomized Methods for Zonotope Enumeration and... | David Gleich | 29m |
Two open problems are presented: empirical eigenvalue histograms for the triangle-weighted Laplacian of Erdős–Rényi graphs consistently defy semicircle and… | ||
| Error Estimation for Randomized Numerical Linear Algebra: Bootstrap Methods | Miles Lopes | 34m |
Uses the bootstrap to estimate the actual error of a single randomized sketched product or least-squares solution by resampling rows of the sketch (multiplier… | ||
| Scalable Algorithmic Primitives for Data Science | Richard Peng | 44m |
Argues that solving graph-structured linear systems becomes practical by combining preconditioning, randomized row sampling and combinatorial sparsifiers… | ||
| Hessian Matrix Inversion in 10^10 Dimensions with Parametric Bootstraps | Uros Seljak | 33m |
Claims a practical way to get marginalized Hessian rows for hyperparameters when latent fields reach 10^10 dimensions, using a generative model and MAP… | ||
| Ridge Regression and Deterministic Ridge Leverage Score Sampling | Shannon McCurdy | 32m |
Greedy selection ranks columns by deterministic ridge leverage scores and picks the top set so that the sampled column matrix C satisfies an… | ||
| Large Scale Stochastic Training of Neural Networks | Amir Gholaminejad | 31m |
Claims a Hessian-driven method that Hessian backpropagation plus adaptive batch size (ABSA) and adversarial/robust regularization matches or improves accuracy… | ||
| Randomized Constrained Matrix Decompositions | Benjamin Erichson | 28m |
Argues that embedding sparse PCA into variable projection and then applying a randomized range finder with power iterations and blocked QR yields a scalable… | ||
| Adventures with Randomized Algebra for Extreme-Scale Signal Processing | Anshumali Shrivastava | 32m |
Shows that locality-sensitive hashing (LSH) turns nearest-neighbor indexing into adaptive sampling with a known collision probability, enabling an unbiased… | ||
| Unbiased Estimates for Linear Regression via Volume Sampling | Michal Derezinski | 36m |
Volume sampling picks D rows with probability proportional to det(X_S^T X_S) and yields an unbiased least‑squares estimator whose expected total loss equals… | ||
| Smoothed Analysis of Low Rank Solutions to Semidefinite Programs via Burer Monteiro Factorization | Praneeth Netrapalli | 35m |
Paper analyzes Burer–Monteiro factorization on the penalized SDP and proves a smoothed‑analysis guarantee: after adding a Gaussian perturbation G to C, every… | ||
| Matrix-free Construction of HSS Representations Using Adaptive Randomized Sampling | Xiaoye S. Li | 30m |
Presents a matrix-free sampling pipeline that builds HSS hierarchies by multiplying A (or A and Aᵀ) with random blocks, adaptively increasing samples in chunks… | ||
| A Fast Algorithm for Computing the Maximum Weight Base in a Linear Matroid | Huy Nguyen | 26m |
Presents an algorithm that outputs the greedy maximum-weight base of a linear matroid in time roughly the number of nonzeros of the input matrix plus r^{ω}… | ||
| Matrix Martingales in Randomized Numerical Linear Algebra | Rasmus Kyng | 34m |
Matrix martingale concentration (a matrix Freedman bound) controls the predictable quadratic variation so randomized incomplete Gaussian elimination yields a… | ||
| Fast Algorithms for Multivariate ODEs arising in Sampling and Learning | Santosh Vempala | 34m |
Proposes a practical algorithm that solves the multivariate ODEs behind Hamiltonian Monte Carlo by approximating trajectories with low‑degree polynomials and… | ||
| Spectrally Robust Graph Isomorphism | Yiannis Koutis | 29m |
Yiannis Koutis (New Jersey Institute of Technology)
https://simons.berkeley.edu/talks/spectrally-robust-graph-isomorphism
Randomized Numerical Linear Algebra… | ||
| Subspace Clustering using Ensembles of K-Subspaces | Laura Balzano | 34m |
K-subspaces is NP-hard in worst case, so the practical method draws many random K-subspaces initializations, builds an averaged co-association matrix… | ||
| nothing matches | ||