
Recent Posts
Archives
Categories
Meta
Monthly Archives: February 2012
Lecture 15: Lowrank approximation of matrices
1. Lowrank approximation of matrices Let be an arbitrary matrix. We assume . We consider the problem of approximating by a lowrank matrix. For example, we could seek to find a rank matrix minimizing . It is known that a … Continue reading
Posted in Uncategorized
Leave a comment
Lecture 14: Spectral sparsifiers
1. Spectral Sparsifiers 1.1. Graph Laplacians Let be an unweighted graph. For notational simplicity, we will think of the vertex set as . Let be the th standard basis vector, meaning that has a in the th coordinate and s … Continue reading
Posted in Uncategorized
Leave a comment
Lecture 13: The AhlswedeWinter Inequality
1. Useful versions of the AhlswedeWinter Inequality Theorem 1 Let be a random, symmetric, positive semidefinite matrix such that . Suppose for some fixed scalar . Let be independent copies of (i.e., independently sampled matrices with the same distribution as … Continue reading
Posted in Uncategorized
1 Comment
Lecture 12: Concentration for sums of random matrices
1. Concentration for sums of random matrices Let be a random real matrix of size . In other words, we have some probability distribution on the space of all matrices, and we let be a matrix obtained by sampling from … Continue reading
Posted in Uncategorized
Leave a comment
Notes on Symmetric Matrices
1. Symmetric Matrices We review some basic results concerning symmetric matrices. All matrices that we discuss are over the real numbers. Let be a real, symmetric matrix of size and let denote the identity matrix. Perhaps the most important and … Continue reading
Posted in Uncategorized
3 Comments
Lecture 11: Graph Sparsifiers
1. Graph Sparsifiers Let be an undirected graph. How well can be approximated by a sparse graph? Such questions have been studied for various notions of approximation. Today we will look at approximating the cuts of the graph. As before, … Continue reading
Posted in Uncategorized
Leave a comment
Lecture 10: Minimum Cuts by the Contraction Algorithm
In the first lecture we discussed the Max Cut problem, which is NPcomplete, and we presented a very simple algorithm that gives a approximation. Today we will discuss the Min Cut problem, which is in P, and we will present … Continue reading
Posted in Uncategorized
Leave a comment