Abstract
It is known that computing the spectral norm and the nuclear norm of a tensor is NP-hard in general. In this paper, we provide neat bounds for the spectral norm and the nuclear norm of a tensor based on tensor partitions. The spectral norm (respectively, the nuclear norm) can be lower and upper bounded by manipulating the spectral norms (respectively, the nuclear norms) of its subtensors. The bounds are sharp in general. When a tensor is partitioned into its matrix slices, our inequalities provide polynomial-time worst-case approximation bounds for computing the spectral norm and the nuclear norm of the tensor.
Original language | English |
---|---|
Pages (from-to) | 1440-1452 |
Journal | SIAM Journal on Matrix Analysis and Applications |
Volume | 37 |
Issue number | 4 |
Early online date | 4 Oct 2016 |
DOIs | |
Publication status | Published - Dec 2016 |
Keywords
- tensor norm
- spectral norm
- nuclear norm
- tensor partition
- block tensor
- approximation bound