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.
展开▼
