Source-linked AI summary
A Symmetry-Preserving Tensor $\star_{\mathbf{M}}$-SVD
Victor Arsenescu, Misha E. Kilmer
TL;DR
Flattening multiway data can discard cross-mode correlations, while reflective symmetry is not exploited by the existing ⋆M-SVD. The paper defines a symmetry-preserving ⋆M-SVD for reflectively symmetric transform-domain slices, retaining optimal Frobenius-norm truncation while halving basis storage. Across ten datasets it matches ordinary tensor SVD recognition rates at 2–11× less storage, except on MUCT, and exceeds ordinary tensor SVD’s best rate on faces under varying illumination.
Problem
Existing ⋆M-SVD methods provide optimal tensor approximations but do not specifically exploit reflective symmetry in multiway data.
Method
The paper defines a symmetry-preserving ⋆M-SVD for ⋆M-symmetric tensors, using a half-size folded tensor to construct a reflection-symmetric left basis whose top half is stored.
Results
Across ten recognition datasets, the symmetric basis matches ordinary tensor SVD rates at 2–11× less storage, except on MUCT, and exceeds ordinary tensor SVD’s best rate on faces under varying illumination.
Takeaways & Limitations
Bilaterally symmetric images can be represented with a symmetry-preserving tensor SVD that reduces basis storage while retaining the ordinary tensor SVD’s recognition rate in most tested datasets.
Takeaways & Limitations
The method loses recognition performance on MUCT, where the authors conclude that the antisymmetric part of the faces matters.
Abstract
from arXiv · showhide
Multiway data such as image collections and video is ubiquitous, but the usual approach of flattening them into matrices discards the cross-mode structure that often carries the signal. The t-product and its generalization, the $\star_{\mathbf{M}}$-product, give a matrix-mimetic tensor algebra with a tensor SVD whose truncation is optimal in the Frobenius norm, just as in the matrix case. Much real data also has internal reflective symmetry: frontal faces, manufactured parts, and leaves are all bilaterally symmetric. We define a symmetry-preserving $\star_{\mathbf{M}}$-SVD that extends the matrix symmetry-preserving SVD of Shah and Sorensen to the $\star_{\mathbf{M}}$-algebra. When a tensor's transform-domain frontal slices are reflectively symmetric, the left basis of its $\star_{\mathbf{M}}$-SVD is symmetric too, so only its top half must be stored. Bilaterally symmetric images, turned on their side and stored as lateral slices, give such a tensor. This construction keeps the symmetric part of each image and stores only half the basis. We then recognize new images by projecting them onto this basis and matching to the nearest training image in coefficient space. Across ten datasets of faces, leaves, butterfly wings, and other objects, the symmetric basis matches the recognition rate of ordinary tensor SVD at 2-11x less basis storage, with the exception of MUCT. On faces under varying illumination it exceeds the best rate the ordinary tensor SVD attains at any storage level.
1. Introduction.
The paper extends the symmetry-preserving matrix SVD to the ⋆M-algebra, exploiting reflective symmetry in transform-domain tensor slices. The resulting factorization preserves symmetric image structure while retaining optimal Frobenius-norm truncation and reducing basis storage.
- Motivation: CP decompositions can be computationally intractable and lack guaranteed best low-rank approximations, while truncated HOSVD is only quasi-optimal in Frobenius norm.The t-product and ⋆M-product instead provide matrix-mimetic tensor SVDs with optimal low-rank approximations under suitable transforms.
- Motivation: Reflective symmetry in multiway data had not been incorporated into the ⋆M-SVD, despite matrix results showing symmetric data can yield symmetric left singular vectors.This gap motivates a dedicated symmetry-preserving tensor construction.
- Tensor symmetry: Bilaterally symmetric images stored as lateral slices produce ⋆M-symmetric tensors whose transform-domain frontal slices are symmetric over their middle rows.This equivalence follows because reflection commutes with the mode-3 transform.
- Method: The symmetry-preserving ⋆M-SVD constructs a reflection-symmetric left basis from a half-size folded tensor, so only its top half must be stored.The factorization has the form A = U ⋆M S ⋆M V^T, with U = 1/√2[U0; R ⋆M U0].
- Method: Because the construction is itself a ⋆M-SVD, truncation remains the best low-rank approximation in the Frobenius norm while using half the basis storage.The standard ⋆M-SVD is computed by taking matrix SVDs of transform-domain frontal slices and transforming the factors back.
- Results: Across ten recognition datasets, the symmetric basis matches ordinary tensor SVD recognition rates at 2–11× less storage, except on MUCT.On faces under varying illumination, it exceeds the ordinary tensor SVD’s best rate at any storage level.
4. The Symmetry-Preserving ⋆M-SVD.
The symmetry-preserving ⋆M-SVD constructs a genuine ⋆M-SVD whose left basis is reflection-symmetric, allowing only its top half to be stored while preserving optimal Frobenius-norm truncation.
- Algorithm: Each transform-domain slice is folded by averaging its top and reflected bottom halves, then factored with one economy SVD on the folded data.The factors are pooled across slices for truncation and can remain in the transform domain during use.
- Symmetry-preserving factorization: Theorem 4.1 gives an economy ⋆M-SVD with a ⋆M-orthonormal, ⋆M-symmetric left basis whose bottom half is determined by reflection.The basis satisfies Uh+1:m,:,: = R ⋆M U1:h,:,:.
- Storage reduction: Only the top half U0 and V need storage because the lower half of the basis equals R ⋆M U0.The algorithm computes U0 from half-size folded transform slices and reconstructs the omitted half by reflection.
- Optimal truncation: Truncating the factorization to the k largest singular tubes gives the best ⋆M-rank-k approximation in Frobenius norm and remains symmetric.This follows because the constructed factorization is itself a ⋆M-SVD.
5. Algorithms.
The algorithms compare symmetry-preserving tensor and matrix constructions, use global energy-based truncation, and reduce basis storage while retaining approximation guarantees.
- Truncation strategy: Algorithm 5.1 pools symmetric-component energies across transform slices and uses one global threshold, so each slice retains a variable number of components.Higher-energy slices retain more components than lower-energy slices.
- Matrix comparison: The sptSVD and the matrix symmetry-preserving SVD store the same number of basis entries when both retain rank k.Each stores only the top half of its basis.
- Approximation comparison: The sptSVD truncation matches or beats the comparable tensor truncation in error while keeping no more components under the stated no-tie condition.The comparison uses the share γ of total Frobenius energy captured by the globally largest squared singular values.
- Cost and storage: The symmetry-preserving method halves basis storage from md to hd = 1/2md while using smaller h × p fold SVDs.Both methods retain the same V factor; the storage reduction applies to U.
- Evaluation objective: The evaluation measures basis storage needed to reach ordinary tensor SVD recognition accuracy because symmetry raises raw accuracy only modestly.The recognition protocol uses the symmetry-preserving basis as the central experimental object.
6. Numerical Experiments.
The experiments evaluate recognition on standardized, aligned image collections using a DCT-based ⋆M construction and account for approximate rather than exact symmetry.
- Data preparation: Every image is converted to grayscale, resized to 64 × 64 pixels, and scaled to [0, 1], with dataset-specific cropping exceptions.Non-square sources are generally center-cropped, while several face datasets are resized directly.
- Illumination setting: Extended Yale B uses 32 mild illuminations per subject for the main experiment, with all 64 illuminations evaluated separately.The mild illuminations are selected by flash angle; the full set appears as “all illuminations” in Table 2.
- Alignment: Face datasets are pre-aligned, while leaf and butterfly images are rotated using segmentation masks so their bilateral axes are vertical before cropping.Beetles, cars, and BIOSCAN receive the same alignment treatment but are omitted from Table 2.
- Symmetry assumption: The method does not assume exact symmetry: folding each image with its reflection produces the nearest symmetric tensor used to build the basis.This accommodates real images that are only approximately symmetric.
- Tensor construction: The tensor uses an orthonormal DCT-II along mode 3, with images placed sideways as lateral slices.In the stated setup, m = n = 64.
- Recognition protocol: Recognition projects test images onto the ⋆M basis and assigns the nearest training image in coefficient space.The DCT replaces the DFT because the image data is strictly real-valued.
1. Split.
The split assigns training and test images within each class, with training images collected as lateral tensor slices.
- Data split: Within each class, images are shuffled and split 70% for training and the remainder for testing, ensuring every retained class appears in both sets.Classes with a single image are dropped.
- Tensor arrangement: The training tensor A stores the p training images as lateral slices, while T⃗ denotes a test image arranged in the same way.
2. Centering.
Training and test images are centered using a mean computed without allowing test images to influence the preprocessing or model-selection steps.
- The mean is subtracted from every training and test image.
- Test images do not contribute to the mean, basis, or truncation choice.
- The centered training tensor is moved to the transform domain once before factorization.
3. Basis.
The symmetric constructions store at most 32 vectors per face and rebuild full vectors from their stored halves during projection.
- At most 32 vectors are stored per face for the symmetric constructions.
- During projection, full vectors are rebuilt from their stored halves for symmetric constructions.
4. Coefficients.
Images are projected face by face into coefficient tensors, and the test label is assigned using nearest-neighbor matching in Frobenius norm.
- Each centered training and test image is projected face by face onto the retained vectors, with coefficient vectors concatenated.
- The test image receives the label of the training image whose coefficient tensor is nearest in Frobenius norm.
5. Match.
Recognition rate measures the fraction of correctly labeled test images and is reported across compression settings and basis constructions.
- Recognition rate is the fraction of test images whose assigned label is correct.
- Recognition rate is computed for every γ and construction, then averaged over five random splits with seeds 0–4.
6. Score.
The symmetry-preserving basis halves per-vector storage and, on most evaluated datasets, reaches ordinary tensor SVD recognition rates with substantially less storage. It improves recognition under varying illumination but reconstructs only symmetric image content and loses on MUCT.
- Constructions: The new basis stores only the top half of each left-basis vector, while plain stores the full vector and rand uses unrelated row pairings.The random control halves storage without preserving object symmetry.
- Metrics: The matched-rate evaluation uses the ordinary method’s best recognition rate minus 0.01 as the target, with storage read from the energy-truncation grid.The reported absolute rates are optimistic because each is a maximum over γ, averaged across five seeds.
- Matched-rate results: 5–11× less storage is observed on face datasets, while leaves and butterfly wings show 2–5× savings; rand generally needs 1.5–4× more storage than new.LFW reaches the target with 678 stored numbers for new versus 4595 for plain, a 6.8× saving.
- Recognition results: On Extended Yale B and AFHQ, new exceeds plain by +0.073 to +0.102 on average over the γ grid, while other listed datasets mainly match plain at lower storage.With 32 mild illuminations, plain peaks at 0.841 whereas new reaches 0.943; with all 64 illuminations, rates drop but the ordering remains.
- Recognition across storage: Figure 3 places new above plain beyond the smallest storage levels on every face dataset, with the largest equal-storage gap under varying illumination.The Extended Yale B gap reaches +0.3 at equal storage, while curves converge near the COIL-100 ceiling.
- Reconstruction and boundaries: The symmetric truncation is Frobenius-optimal at half storage for perfectly symmetric data, but real-image reconstruction is limited to the symmetric component.MUCT is the only face dataset where new never reaches ordinary recognition, indicating that folding loses unrecovered information there.
7. Conclusions and Future Work.
The paper identifies approximate symmetry, transform selection, and multiple symmetry axes as directions for future work. It cautions that imposing additional symmetry can trade recognition accuracy for further storage savings.
- Future work should characterize how performance degrades when the data is only approximately symmetric.
- A data-adapted orthogonal transform could improve compression while preserving the method’s reliance on orthogonality.
- The fold-and-halve construction may extend to objects with multiple symmetry axes, enabling further storage reduction.
- Additional imposed symmetry can eventually reduce recognition rate because it discards more of the data.
Data sources.
The recognition datasets are drawn from documented face, vehicle, insect, and beetle data sources.
- The recognition datasets and their sources are documented in the paper's Section 6.
- The listed sources include Extended Yale B and original Yale face datasets, Stanford Cars, BIOSCAN, and NEON ground beetles.