Tensor-structured sketching for constrained optimizations

Constrained least squares are fundamental in applied math, statistics and many other disciplines. The memory and computation costs are expensive in practice due to high-dimensional input data. We apply the so-called "sketching" strategy to project the problem onto a space of a much lower dimension while maintaining the approximation accuracy. Tensor structure often appears in the data matrices of optimization problems. In this talk, we will discuss: 1. Sketching designs for optimizations that have special tensor format. 2. Theoretical guarantees of tensor sketching for optimizations with general constrained sets, for instance, linear regression and sparse recovery. The sketching dimension depends on a statistical complexity that characterizes the geometry of the underlying problem.