Operator norm inequalities between tensor unfoldings on the partition lattice

Miaoyan Wang, Khanh Dao Duc, Jonathan Fischer, Yun S. Song

Introduction

Tensors, or multi-dimensional arrays, are fundamental objects in modern data science, appearing in fields ranging from signal processing to deep learning. Despite their ubiquity, tensors present significant computational challenges compared to matrices. A standard technique to circumvent these difficulties is "unfolding" or "matricizing" a tensor—rearranging its entries into a matrix to leverage established linear algebraic tools. However, the theoretical implications of these transformations on the tensor's intrinsic properties, specifically its operator norms, have historically been under-explored. This paper establishes a rigorous framework to map the "norm landscape" of tensor unfoldings using the logic of set partitions.

The Partition Lattice Framework

The central innovation of this work is the use of the partition lattice to organize all possible ways to unfold a $k$-order tensor. Each way to group the modes (dimensions) of a tensor corresponds to a partition $\pi$ of the set $\{1, \dots, k\}$. These partitions form a lattice where one partition is "finer" or "coarser" than another based on whether its blocks are subsets of the blocks of another.

The partition lattice for an order-4 tensor, illustrating the hierarchical relationship between different unfolding configurations.

In this framework, the finest partition (at the bottom of the lattice, e.g., $\{\{1\}, \{2\}, \{3\}, \{4\}\}$) represents the original tensor structure, while the coarsest partition (at the top, e.g., $\{\{1, 2, 3, 4\}\}$) represents the fully vectorized form. The authors define a generalized unfolding operation where any partition $\pi$ induces a specific lower-order tensor representation.

Monotonicity and the Norm Landscape

The researchers focus on the $l^p$ operator norm, with a particular emphasis on the spectral norm ($p=2$). Unlike standard matrix norms, the tensor spectral norm is defined via multilinear functionals and is generally NP-hard to compute.

A key insight of the paper is the monotonicity of flattening: as a tensor is unfolded from a finer partition to a coarser one, its spectral norm monotonically increases. Specifically, the original tensor possesses the smallest spectral norm, while the fully vectorized version (equivalent to the Frobenius norm) possesses the largest. This result implies that the spectral norm preserves the partial order of the partition lattice, allowing researchers to predict how norm values will shift when merging or splitting tensor dimensions.

Structured Tensors and Invariance

While flattening generally increases the norm, the authors identify a specific class of "structured" tensors where the norm remains invariant. They introduce the concept of $\pi$-orthogonal decomposability ($\pi$-OD). For tensors exhibiting this structure, the spectral norm stays exactly the same across a range of unfoldings—specifically, any unfolding that is coarser than $\pi$ but finer than total vectorization. This provides a theoretical justification for why matricization can be performed without information loss in certain high-dimensional data contexts.

Quantitative Bounds and Results

Beyond qualitative monotonicity, the paper provides sharp polynomial bounds on the growth of the norm.

  • Theorem 4.8 provides a concrete formula to bound the ratio of spectral norms between any two arbitrary unfoldings $\pi_1$ and $\pi_2$.
  • Corollary 4.10 establishes a relationship between the Frobenius norm $\|\mathcal{A}\|_F$ and the spectral norm $\|\mathcal{A}\|_\sigma$: $$\|\mathcal{A}\|_F \le \sqrt{\frac{\text{dim}(\mathcal{A})}{\max d_n}} \|\mathcal{A}\|_\sigma$$ where $\text{dim}(\mathcal{A})$ is the total number of entries and $\max d_n$ is the largest single dimension. This bound is more precise than previous results in the literature.

Conclusion and Future Directions

This work provides the first comprehensive map of how unfolding operations affect tensor operator norms. While the derived bounds are polynomial and may scale poorly in extremely high dimensions (the "curse of dimensionality"), the framework offers a principled way to choose unfolding strategies for algorithms like the Higher-Order SVD (HOSVD). Future research may explore whether $\pi$-OD is a necessary condition for norm invariance and how these insights can be directly integrated into more efficient tensor decomposition algorithms.

Summary updated

Abstract

Interest in higher-order tensors has recently surged in data-intensive fields, with a wide range of applications including image processing, blind source separation, community detection, and feature extraction. A common paradigm in tensor-related algorithms advocates unfolding (or flattening) the tensor into a matrix and applying classical methods developed for matrices. Despite the popularity of such techniques, how the functional properties of a tensor changes upon unfolding is currently not well understood. In contrast to the body of existing work which has focused almost exclusively on matricizations, we here consider all possible unfoldings of an order-$k$ tensor, which are in one-to-one correspondence with the set of partitions of $\{1,\ldots,k\}$. We derive general inequalities between the $l^p$-norms of arbitrary unfoldings defined on the partition lattice. In particular, we demonstrate how the spectral norm ($p=2$) of a tensor is bounded by that of its unfoldings, and obtain an improved upper bound on the ratio of the Frobenius norm to the spectral norm of an arbitrary tensor. For specially-structured tensors satisfying a generalized definition of orthogonal decomposability, we prove that the spectral norm remains invariant under specific subsets of unfolding operations.
BibTeX
@inproceedings{wang2017operator,
  author = {Miaoyan Wang and Khanh Dao Duc and Jonathan Fischer and Yun S. Song},
  title = {{Operator norm inequalities between tensor unfoldings on the partition lattice}},
  booktitle = {Linear},
  year = {2017},
  doi = {10.1016/j.laa.2017.01.017},
}
Figure