Computational Methods for Science, Machine Learning, and Quantum Information
Today, I want to talk about the generalized Nyström approximation, which I regard as the one of the big three approaches to constructing a low-rank approximation to matrix. Understanding this approximation, under what conditions it works and the sharpest possible error bounds for it, is a subject of two recent papers of mine: On the Read more
Let be random vectors and let denote their tensor product. Assume the vectors are isotropic, in the sense that The vector inherits the isotropy property as well . As a consequence, we can use the vector to form an unbiased estimator for the matrix trace . Trace estimation has been a frequent topic Read more
If a polynomial function is trapped in a box, how much can it wiggle? This question is answered by Markov s inequality, which states that for a degree- polynomial that maps into , it holds that (1) That is, if a polynomial is trapped within a square box , the fastest it can wiggle—as measured Read more
I am excited to share that my paper Does block size matter in randomized block Krylov low-rank approximation? has recently been released on arXiv. In that paper, we study the randomized block Krylov iteration (RBKI) algorithm for low-rank approximation. Existing results show that RBKI is efficient at producing rank- approximations with a large block size Read more
Gaussian random variables are wonderful, and there are lots of clever tricks for doing computations with them. One particularly nice tool is the Gaussian integration by parts formula, which I learned from my PhD advisor Joel Tropp. Here it is: Gaussian integration by parts. Let be a standard Gaussian random variable. Then . This formula Read more
Five years ago today, I embarked on a crazy experiment. It was the summer after I finished my undergraduate degree, and I was filled with lots of exciting things I learned from my mentor Shiv Chandrasekaran and my own self-study. I kept asking, Why did no one teach me that subject in this way? If Read more
The randomized Kaczmarz method is a method for solving systems of linear equations: (1) Throughout this post, the matrix will have dimensions . Beginning from an initial iterate , randomized Kaczmarz works as follows. For : What selection probabilities should we use? The answer to this question may depend on whether the system (1) Read more
Every once in a while, there s a paper that comes out that is so delightful that I can t help share it on this blog, and I ve started a little series Neat Randomized Algorithms for exactly this purpose. Today s entry into this collection is The Polar Express: Optimal Matrix Sign Methods and their Application to the Read more
In the previous posts, we ve been using eigenvalues to understand the mixing of reversible Markov chains. Our main convergence result was as follows: Here, denotes the distribution of the chain at time , denotes the stationary distribution, denotes the divergence, and denote the decreasingly ordered eigenvalues of the Markov transition matrix . Bounding Read more
The Schur product theorem states that the entrywise product of two positive semidefinite matrices is also positive semidefinite. This post will present every proof I know for this theorem, and I intend to edit it to add additional proofs if I learn of them. (Please reach out if you know another!) My goal in this Read more