Tensor sparsification via a bound on the spectral norm of random tensors

2010/05/26 by Nguyen, Nam H., Drineas, Petros, Tran, Trac D. · 4 citations
#FOS: Mathematics #G.1 #G.3 #Numerical Analysis (math.NA)

paper · doi:10.48550/arxiv.1005.4732

Abstract

Given an order-d tensor \tensor A ∈ \R^{n × n ×...× n}, we present a simple, element-wise sparsification algorithm that zeroes out all sufficiently small elements of \tensor A, keeps all sufficiently large elements of \tensor A, and retains some of the remaining elements with probabilities proportional to the square of their magnitudes. We analyze the approximation accuracy of the proposed algorithm using a powerful inequality that we derive. This inequality bounds the spectral norm of a random tensor and is of independent interest. As a result, we obtain novel bounds for the tensor sparsification problem.

Cited by

• Causal Inference on Sequential Treatments via Tensor Completion
• On Spectral Learning for Odeco Tensors: Perturbation, Initialization, and Algorithms
• On zeros and algorithms for disordered systems: mean-field spin glasses
• Balanced multi-species spin glasses

Related

• Effective Tensor Sketching via Sparsification
• Spectral norm of random tensors
• A New Sampling Technique for Tensors
• Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors
• Spectral algorithms for tensor completion