Random Vectors in High Dimensions

This chapter begins the study of random vectors in high dimensions, starting by showing their norm concentrates. We give a probabilistic proof of the Grothendieck inequality and apply it to semidefinite optimization. We explore a semidefinite relaxation for the maximum cut, presenting the Goemans–Williamson randomized approximation algorithm. We also give an alternative proof of the Grothendieck inequality with nearly the best known constant using the kernel trick, a method widely used in machine learning. The exercises explore invariant ensembles of random matrix theory, various versions of the Grothendieck inequality, semidefinite relaxations, and the notion of entropy.