Source-linked AI summary
Compound Rank-k Projections for Bilinear Analysis
Xiaojun Chang, Feiping Nie, Sen Wang, Yi Yang, Xiaofang Zhou, Chengqi Zhang
TL;DR
Existing discriminant-analysis methods face limitations from vectorization, restricted projection flexibility, over-fitting trade-offs, and convergence concerns. CRP directly analyzes matrices using multiple rank-k projection models, preserving spatial correlations while reducing complexity and guaranteeing monotonic objective improvement. The paper reports better classification performance than compared algorithms, including classical two-dimensional LDA.
Problem
Existing methods either vectorize matrices, limiting correlation preservation and increasing computation, or use a single projection model with flexibility and over-fitting trade-offs.
Method
CRP performs bilinear analysis directly on matrices using multiple orthogonal rank-k projection models and alternating optimization.
Results
CRP achieves better performance than compared algorithms in classification accuracy using two different classifiers.
Takeaways & Limitations
CRP preserves spatial correlations, decreases computation complexity, and provides a larger search space with monotonically increasing objective values.
Takeaways & Limitations
The method retains a trade-off between projection degree of freedom and avoidance of over-fitting.
Abstract
from arXiv · showhide
In many real-world applications, data are represented by matrices or high-order tensors. Despite the promising performance, the existing two-dimensional discriminant analysis algorithms employ a single projection model to exploit the discriminant information for projection, making the model less flexible. In this paper, we propose a novel Compound Rank-k Projection (CRP) algorithm for bilinear analysis. CRP deals with matrices directly without transforming them into vectors, and it therefore preserves the correlations within the matrix and decreases the computation complexity. Different from the existing two dimensional discriminant analysis algorithms, objective function values of CRP increase monotonically.In addition, CRP utilizes multiple rank-k projection models to enable a larger search space in which the optimal solution can be found. In this way, the discriminant ability is enhanced.
1 INTRODUCTION
Existing discriminant-analysis methods face trade-offs involving matrix structure, computational cost, convergence, flexibility, and over-fitting. CRP addresses these limitations with multiple rank-k projection models and explicitly guaranteed convergence.
- Vectorizing matrices erases within-matrix correlations, increases dimensionality, and dramatically raises computational burden.
- Two-dimensional discriminant analysis preserves spatial correlations and reduces computation by operating directly on matrix representations.
- Existing methods trade degree of freedom against over-fitting: full-rank LDA is flexible but overfits, whereas 2DLDA better avoids over-fitting with smaller flexibility.
- CRP uses multiple orthogonal projection models to obtain more discriminant directions from different orthogonal bases.
- CRP directly handles matrices, preserves spatial correlations, reduces complexity, and explicitly guarantees convergence.
2 RELATED WORK
Classical LDA projects vectorized data using between-class and within-class scatter, while 2DLDA retains matrix structure through bilinear transformations. Iterative 2DLDA optimization may lack monotonicity guarantees.
- Classical LDA seeks a transformation that separates different classes and compacts samples from the same class in a lower-dimensional subspace.
- LDA defines between-class and within-class scatter matrices to formulate its discriminant objective.
- The LDA objective maximizes transformed between-class scatter while minimizing transformed within-class scatter, solvable through eigen-decomposition.
- 2DLDA uses matrix representations and seeks a single pair of transformation matrices, U and V, for bilinear projection.
- The classical 2DLDA iterative algorithm cannot guarantee monotonic objective-function increase and complicates termination-criterion selection.
3 COMPOUND RANK-k PROJECTION
CRP seeks multiple projection-matrix pairs for matrix-valued data, combining orthogonal rank-k models with regularization and alternating optimization. Its design balances flexibility against over-fitting.
- CRP seeks h sets of projection matrices U_i and V_i, each producing a rank-k bilinear projection into h-dimensional subspaces.
- The multiple models create a larger search space, increase degree of freedom, and enhance discriminant ability.
- The rank choice reflects a trade-off: full-rank projections maximize degree of freedom but induce over-fitting, while CRP is designed to benefit from this balance.
- Orthogonal transformations project data into different orthogonal bases so information from differing perspectives can be obtained.
- A regularization term is added to avoid over-fitting and singularity of the within-class scatter matrix.
- For fixed V_p, CRP optimizes U_p, then updates V_p using the obtained U_p, with a monotonic increase in the objective function.
4 OPTIMIZATION
CRP optimizes alternating projection matrices by rewriting subproblems as generalized eigen-decomposition problems. With k = 2, its stated complexity is substantially lower than classical LDA for the example given.
- For fixed V_p, CRP rewrites the objective function as a generalized eigen-decomposition problem to obtain optimal U_p.
- For fixed U_p, CRP applies analogous transformations to compute optimal V_p.
- The alternating optimizations of U_p and V_p are iterated until convergence.
- With k = 2, CRP has total time complexity O((k max(l1, l2))3).
- For Coil20 with 32 × 32 data, CRP requires O((2 × 32)3), compared with classical LDA complexity beginning at O((1024...).
5 CONVERGENCE ANALYSIS
Algorithm 1 is presented as the optimization procedure for CRP, with updates for projection matrices and training data. The paper proves that its objective function increases monotonically until convergence.
- The objective function value increases monotonically until convergence.
- Algorithm 1 is the optimization algorithm for CRP.
- The algorithm processes class data and computes the global mean before optimization.
- The procedure initializes Vp, updates vp and up iteratively, and updates the training data according to Eq. (3).
21 end
The convergence proof alternates optimization over U and V while holding the other projection fixed. Convex subproblems and combined inequalities establish monotonic objective-function improvement.
- After each iteration, the method fixes V and optimizes U, then fixes U and optimizes V.This alternating procedure is used because U and V are difficult to compute simultaneously.
- For fixed V, the objective becomes a convex optimization problem with respect to U.
- The corresponding updates are obtained by setting the derivative with respect to U to zero.
- Integrating the inequalities from the U and V updates shows that the objective function value increases monotonically.The paper states that this establishes Theorem 1.
6 EXPERIMENT
The experiments evaluate CRP’s convergence, sensitivity to k and initialization, and classification performance across multiple datasets and competing methods. CRP converges quickly, performs best across reported comparisons, and benefits from multiple projection models, especially with limited training data.
- Experimental design: Experiments evaluate convergence, k sensitivity, initialization variance, and classification performance across several multimedia-analysis datasets.The datasets cover face, object, facial-expression, head-pose, and handwritten-digit recognition, using accuracy as the evaluation metric.
- Convergence demonstration: CRP converges fast across five datasets, with convergence occurring within ten iterations in most cases.The objective-function value is plotted against iteration number, and other projection models show similar behavior.
- Performance variance with k: On UUIm, accuracy increases from 29.6% at k=1 to about 32.5% at k=2, then remains stable as k increases.The authors empirically set k to 2 for subsequent experiments to reduce computation complexity while obtaining decent results.
- Performance with different initializations: CRP obtains good local optima across different initializations.The tested initializations set diagonal elements of V to 0.5, 1, 2, or random values.
- Classification performance comparison: CRP outperforms the other seven algorithms and retains an advantage when training data are insufficient.With three training samples per class on CVL, CRP’s accuracy relatively exceeds 2DLDA by 107%.
- Classification performance comparison: As training samples increase, all compared methods improve, while CRP consistently performs better than the alternatives.On UUIm, increasing training data from 3 × c to 20 × c raises Bilinear SVM accuracy from 28.2 to 61.2 and CRP accuracy from 32.5 to 64.2.
7 CONCLUSION
CRP uses multiple projection models while operating directly on matrix representations, preserving spatial correlations and reducing computation complexity. The experiments report higher classification accuracy than compared algorithms using two classifiers.
- CRP directly processes matrices rather than vectorizing them, preserving spatial correlations and reducing computation complexity.
- Multiple projection models give CRP a larger search space for obtaining discriminant projections.
- CRP’s objective function increases monotonically, so its optimization can obtain the optimum.
- The method balances projection degree of freedom against avoiding over-fitting through its rank-k projection design.
- The experiments report that CRP outperforms the compared algorithms in classification accuracy with two different classifiers.
APPENDIX LEMMAS USED IN THIS PAPER
The appendix records algebraic identities used to relate matrix operations, vectorization, trace expressions, and Kronecker products. These lemmas support transformations involving bilinear projections and matrix representations.
- The appendix uses vectorization to rewrite matrix expressions in terms of Kronecker products.
- The appendix defines vec(·) as the vectorization of a matrix and ⊗ as the Kronecker product.
- For projection factors U and V, the appendix gives vec(UV^T)^T vec(UV^T) = Tr(U^T U V^T V).
- Trace definitions and dot-product properties are used to derive equivalent expressions for matrix products.
- Lemma 4 states the vectorization identity vec(AXB) = (B^T ⊗ A)vec(X).