Compressed Sensing with Quantized Tensor Trains (QTTs)

The storage and recovery of a vector of length $2^d$ can become prohibitively expensive as $d$ grows, a manifestation of the curse of dimensionality. For certain structured functions and multiscale quantities, the resulting discretized vectors admit compact quantized tensor train (QTT) representations after binary tensorization: a length-$2^d$ vector is reshaped into a $d$-way binary tensor with low tensor-train (TT) rank. Motivated by this construction, we study compressed sensing of tensorized signals that combine bounded TT rank with sparse low-order interaction structure, using randomly sampled Walsh–Hadamard measurements. For this structured model class, we establish a uniform restricted isometry property and derive a measurement condition guaranteeing uniqueness of noiseless recovery. We also propose a structure-aware initializer for the alternating linear scheme (ALS), obtained by projecting the adjoint backprojection onto the low-order interaction space before applying TT-SVD. We prove a uniform initialization error bound whose measurement requirement, for fixed structural parameters, grows polynomially with the tensor order $d$ rather than with the ambient dimension $2^d$. Numerical experiments support the predicted RIP and initialization scaling and demonstrate more reliable ALS recovery.