Sparse and Low-rank Tensor Estimation via Cubic Sketchings.

Area of Science:

• Tensor decomposition
• High-dimensional statistics
• Machine learning

Background:

• Sparse and low-rank tensor estimation is crucial for analyzing complex datasets.
• Existing methods often struggle with high-dimensional data and noise.
• Cubic sketchings offer a computationally efficient approach to dimensionality reduction.

Purpose of the Study:

• To propose a general framework for sparse and low-rank tensor estimation from cubic sketchings.
• To develop an efficient non-convex optimization algorithm for tensor decomposition.
• To provide theoretical guarantees for the recovery performance in both noiseless and noisy scenarios.

Main Methods:

• A two-stage non-convex optimization approach combining sparse tensor decomposition and thresholded gradient descent.
• Non-asymptotic analysis to understand the relationship between optimization and statistical errors.
• Derivation of novel high-order concentration inequalities for sub-Gaussian tensors.

Main Results:

• The proposed method achieves exact recovery in the noiseless case and stable recovery with high probability in the noisy case.
• The procedure is shown to be rate-optimal under specific conditions.
• New concentration inequalities for high-moment sub-Gaussian tensors are established.

Conclusions:

• The developed framework and algorithm provide a robust solution for sparse and low-rank tensor estimation.
• The theoretical analysis offers valuable insights into the performance limitations and capabilities of tensor recovery methods.
• The tensor formulation demonstrates potential applications in identifying high-order interactions in high-dimensional linear regression.