Workshop on Succinct Data Representations and Applications (Simons Institute Big Data 2013)
2013-09-16..2013-09-19
Berkeley, United States
[Information Theory, Learning and Big Data (Simons Institute, 2015), Sketching and Algorithm Design 2023, Randomized Numerical Linear Algebra and Applications 2018, Sublinear Algorithms and Nearest-Neighbor Search, Semidefinite Optimization, Approximation and Applications 2014, Parallel and Distributed Algorithms for Inference and Optimization (Simons Institute, Oct. 21–24, 2013)]
who it's for
research scientists in algorithms and theory, algorithm engineers, data engineers, machine learning researchers, machine learning engineers, computational statisticians
topics
input-sparsity time embeddings; L2 and L1 subspace embeddings; randomized numerical linear algebra; deterministic frequent-directions sketch; leverage-score row and column sampling; spectral sparsification via effective resistance; memory-limited streaming PCA; volume and adaptive sampling for low-rank; L0 and homomorphic sketching; min-wise hashing for large-scale regression; Johnson-Lindenstrauss projections for sketches; local Voronoi-based clustering certificates
| title | author | length |
|---|---|---|
| Input-sparsity Time Algorithms for Embeddings and Regression Problems | Michael Mahoney | 48m |
Claims that L2 and L1 subspace embeddings can be built in near input-sparsity time by using a projection Pi = S D where D is a random diagonal (±1 for L2… | ||
| Something for Almost Nothing: Advances in Sub-Linear Time Algorithms | Ronitt Rubinfeld | 44m |
Algorithms decide properties and approximate values without reading all data by sampling, random orderings, and simulating local procedures. Key concrete… | ||
| Randomized Numerical Linear Algebra | Petros Drineas | 48m |
Randomized row/column sampling with R = Θ(d/ε) scaled rows gives 1+ε relative‑error solutions to overconstrained least‑squares by sampling with leverage scores… | ||
| Simple and Deterministic Matrix Sketches | Edo Liberty | 31m |
An algorithm called deterministic frequent-directions maintains an L-column sketch B so AA^T − BB^T has operator norm ≤ ε||A||_F^2 when L = 2/ε, by SVD’ing the… | ||
| Optimizing with Tensors | Ravi Kannan | 36m |
Reductions show Max‑3SAT and planted‑clique become problems of maximizing a cubic form over unit vectors by encoding clauses or parity into an n×n×n tensor; a… | ||
| Homomorphic Sketches: Shrinking Big Data without Sacrificing Structure | Andrew McGregor | 48m |
Shows a recipe to compress each row of an n-by-n adjacency matrix into polylog(n) bits per node by encoding signed incidence vectors and applying an… | ||
| Power to the Points: Local Certificates for Clusterings | Suresh Venkatasubramanian | 37m |
Proposes local, per-point confidence by inserting a query into the clustering’s Voronoi/power diagram and measuring the fractional area it steals to produce an… | ||
| How Robust are Linear Sketches to Adaptive Inputs? | David P. Woodruff | 44m |
Shows a reconstruction attack that, given oracle access to any r‑row linear sketch, uses Gaussian query distribution and polynomially many adaptive queries to… | ||
| Nimble Algorithms for Cloud Computing | Santosh Vempala | 47m |
Defines sublinear communication algorithms that use polynomial time/space but exchange far less than the data. Shows frequency moments across S servers by… | ||
| Sampling for Subset Selection and Applications | Amit Deshpande | 35m |
Shows that picking roughly k/ε rows (or O(k/ε) columns) by adaptive sampling or volume sampling yields a 1+ε low-rank approximation in time about n·d·k/ε… | ||
| Spectral Sparsification of Graphs | Nikhil Srivastava | 46m |
Claim: every weighted undirected graph admits a spectral sparsifier with about N log N / ε^2 edges that preserves the Laplacian quadratic form up to 1±ε… | ||
| Fast Testing of Graph Properties | Artur Czumaj | 41m |
Characterizes what's testable fast and where costs hide: dense graphs (adjacency matrix) admit constant-query testers for all hereditary properties but with… | ||
| Inferring Structural Properties: Graphs and Bridges | Anna Gilbert | 48m |
Wireless sensors sample bridge vibration and modal shapes are recovered by taking an SVD of the time-by-sensor matrix after aggressive sketching. Using… | ||
| Convex Relaxations for Permutation Problems | Alexandre d'Aspremont | 47m |
Claims that spectral ordering via the Fiedler vector spectral ordering recovers seriation exactly for noiseless R-matrices, and that seriation equals a two-sum… | ||
| Computational and Statistical Tradeoffs via Convex Relaxation | Venkat Chandrasekaran | 43m |
Claim: with abundant IID data extra samples let one use sample mean then projection on successively weaker convex relaxations to cut runtime while keeping… | ||
| Memory Limited, Streaming PCA | Constantine Caramanis | 39m |
Algorithm recovers the top principal component in the Gaussian spiked identity model using a streaming power method that never forms the p×p covariance and… | ||
| Noisy Estimation of Simultaneously Structured Models | Maryam Fazel | 45m |
Examines recovery of models that are simultaneously structured (e.g. low-rank and sparse or lifted phase retrieval) and shows that naively minimizing a convex… | ||
| Min-Wise Hashing for Large-Scale Regression and Classification | Nicolai Meinshausen | 37m |
Compresses very large sparse design matrices into a dense sketch via random permutations and signed hashing, proving an unbiased approximation to Xβ and giving… | ||
| Variable Selection with Error Control: Another Look at Stability Selection | Richard Samworth | 48m |
Introduces complementary-pair stability selection: apply any base selector to random half-samples and their complements, aggregate selections, and keep… | ||
| Mixed and Covariate-Dependent Graphical Models | Liza Levina | 38m |
Proposes a covariate-dependent Ising with linear parameters estimated by nodewise penalized logistic regressions (neighborhood selection) and L1 penalties… | ||
| Succinct Representations and Efficient Algorithms Based on Linear Programming | Sudipto Guha | 47m |
Shows how to compute a 1 - ε approximation to maximum cardinality matching in non‑bipartite graphs in a semi‑streaming/map‑reduce style model using p/ε passes… | ||
| Dimensionality Reduction Via Sparse Matrices | Jelani Nelson | 42m |
Shows sparse Johnson–Lindenstrauss matrices that embed N points to m = O(ε^{-2} log N) rows while reducing per-column nonzeros s by an Θ(ε) factor versus prior… | ||
| Probabilistic Hashing Methods for Succinct Data Representations and Applications | Ping Li | 39m |
Uses alpha-stable random projections (alpha near zero and maximally-skewed beta=1) to get extremely sparse, noise-robust compressive sensing that recovers k=2… | ||
| Optimal Detection of Sparse Signal Segments | Ming Yuan | 39m |
Derives precise detection thresholds and practical procedures for sparse segments in a length-n sequence, proving optimal rates and phase transitions. Uses a… | ||
| Two Concise Representations for High-Dimensional Visual Data | John Wright | 51m |
Derives two concrete representations and proofs: images under varying illumination admit a low-rank + sparse decomposition enabling convex recovery (exact… | ||
| Structured Sparsity-Inducing Norms Through Submodular Functions | Francis Bach | 44m |
Derives convex sparsity norms from nondecreasing submodular set functions and proves the Lovász extension is the convex envelope of any penalty that depends on… | ||
| Going Off the Grid | Benjamin Recht | 40m |
Frames sparse sum-of-sinusoids with continuous frequencies as a convex recovery problem using the atomic norm, proves exact and stable recovery under a… | ||
| nothing matches | ||