  Constrained least squares problems arise in many applications. Their memory
and computation costs are expensive in practice involving high-dimensional
input data. We employ the so-called "sketching" strategy to project the least
squares problem onto a space of a much lower "sketching dimension" via a random
sketching matrix. The key idea of sketching is to reduce the dimension of the
problem as much as possible while maintaining the approximation accuracy.
  Tensor structure is often present in the data matrices of least squares,
including linearized inverse problems and tensor decompositions. In this work,
we utilize a general class of row-wise tensorized sub-Gaussian matrices as
sketching matrices in constrained optimizations for the sketching design's
compatibility with tensor structures. We provide theoretical guarantees on the
sketching dimension in terms of error criterion and probability failure rate.
In the context of unconstrained linear regressions, we obtain an optimal
estimate for the sketching dimension. For optimization problems with general
constraint sets, we show that the sketching dimension depends on a statistical
complexity that characterizes the geometry of the underlying problems. Our
theories are demonstrated in a few concrete examples, including unconstrained
linear regression and sparse recovery problems.
