Algorithms for Big Data (COMPSCI 229r), Lecture 15

Algorithms for Big Data (COMPSCI 229r), Lecture 15 Approximate matrix multiplication with Frobenius error via sampling / JL, matrix median trick, subspace embeddings.

Algorithms for Big Data (COMPSCI 229r), Lecture 14

Algorithms for Big Data (COMPSCI 229r), Lecture 14 Sparse JL proof wrap-up, Fast JL Transform, approximate nearest neighbor.

Algorithms for Big Data (COMPSCI 229r), Lecture 13

Algorithms for Big Data (COMPSCI 229r), Lecture 13 This lecture explores instance-wise dimensionality reduction beyond worst-case analysis. It covers the proof of Gordon's theorem as an extension of the Johnson-Lindenstrauss lemma and discusses techniques for accelerating the computation of dimensionality reduction, including the use of sparse matrices to improve performance while maintaining desired accuracy guarantees.

Algorithms for Big Data (COMPSCI 229r), Lecture 12

Algorithms for Big Data (COMPSCI 229r), Lecture 12 This lecture explores lower bounds for the Johnson-Lindenstrauss lemma, distinguishing between distributional and metric versions. It introduces Gordon's theorem as a method for dimensionality reduction on infinite sets, shifting focus from worst-case analysis to instance-specific geometric properties of vector databases

Algorithms for Big Data (COMPSCI 229r), Lecture 11

Algorithms for Big Data (COMPSCI 229r), Lecture 11 Khintchine, decoupling, Hanson-Wright, proof of distributional JL lemma.