TL;DR
This paper introduces a novel "multiresolution low-rank tensor format" that represents tensors as a sum of compressed tensors at different scales. This approach achieves significantly higher compression ratios than existing methods like the tensor-train format, especially for data with multiple length-scales, while maintaining accuracy.
What Problem Does This Paper Address?
High-dimensional data is often represented by tensors. As the dimensions of these tensors grow, storing and processing them becomes computationally expensive and memory-intensive. Existing methods like the tensor-train format and canonical decomposition offer compression by exploiting low-rank structures. However, these methods can struggle with tensors that have multiple inherent length-scales, where the overall tensor might not be low-rank, even if its components at different scales are. This is particularly problematic for emerging edge computing devices with limited memory. This paper addresses the challenge of efficiently compressing and representing such multiscale tensors.
Methods
The core contribution is the multiresolution tensor format (MSF). This format represents a tensor as a sum of compressed tensors, each defined on a grid of increasing coarseness. The key idea is to capture low-rank information at each scale, leading to better overall compression.
The paper introduces two fundamental operations:
ext_l(T)(block extension): This operation replaces each entry of a tensorTwith a block of a specified size, effectively "extending" the tensor to a coarser grid.ave_l(S)(averaging): This is the inverse operation ofext_l, averaging entries within blocks to move to a coarser grid.
An alternating algorithm is proposed to decompose a given tensor into this multiresolution format. This algorithm iteratively refines the approximation at each scale, aiming to minimize the overall error. The paper also discusses the closedness and stability of this new format, which are crucial for theoretical guarantees and practical applications.
Datasets
The paper evaluates its method on six real-world datasets:
- A motivating example function with multiple length-scales.
- Two greyscale images (2048x2048 pixels) from [8, 23].
- Three hyperspectral wavelength datasets from [35, 24, 26].
- Video recordings of three different scenes [22].
Key Insights and Ideas
- Exploiting Multiscale Structure: The fundamental insight is that by explicitly representing a tensor across multiple scales, we can achieve better compression than methods that only look for a single low-rank approximation.
- "Beating" the Eckart-Young Theorem: For matrices (2D tensors), the multiresolution format can achieve lower approximation error for a given storage cost than the standard truncated Singular Value Decomposition (SVD), which is the optimal low-rank approximation according to the Eckart-Young theorem.
- Hierarchical Compression: The
ext_landave_loperations provide a natural way to move between different levels of grid resolution, enabling a hierarchical compression strategy. - Algorithm Design: The alternating algorithm provides a practical way to compute the multiresolution decomposition, iteratively improving the approximation at each scale.
Key Results
- Higher Compression Ratios: For dimensions higher than two, the multiresolution format achieves higher compression than the tensor-train format on all six real-world datasets. In some cases, compression ratios are several times larger.
- Improved Accuracy for Given Storage: The multiresolution format can achieve better accuracy for a fixed storage budget compared to standard tensor formats.
- Visual Quality: Compressed images using the multiresolution format show visibly clearer features and lower approximation error for the same compression ratio.
- Theoretical Guarantees: The paper proves local convergence guarantees for the proposed alternating algorithm.
Limitations and Future Work
- Runtime: The paper notes that achieving higher compression comes at the expense of higher runtimes compared to the tensor-train format.
- Closedness: The multiresolution format is not always closed, meaning that optimal approximations may not always exist within the format. This is particularly true for the tensor-train format as the underlying compression method.
- Future Work: The authors suggest that for lower accuracy requirements, the multiresolution format offers significant storage gains. They also mention that randomized algorithms could be used to lower the total computational time. Further investigation into the closedness and stability properties for various underlying tensor formats is also implied.
Summary updated