Bounds on the spectral norm and the nuclear norm of a tensor based on tensor partitions

Research output: Contribution to journalArticlepeer-review

680 Downloads (Pure)

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 languageEnglish
Pages (from-to)1440-1452
JournalSIAM Journal on Matrix Analysis and Applications
Volume37
Issue number4
Early online date4 Oct 2016
DOIs
Publication statusPublished - Dec 2016

Keywords

  • tensor norm
  • spectral norm
  • nuclear norm
  • tensor partition
  • block tensor
  • approximation bound

Fingerprint

Dive into the research topics of 'Bounds on the spectral norm and the nuclear norm of a tensor based on tensor partitions'. Together they form a unique fingerprint.

Cite this