PaperlayerView exact revision on arXiv

Source-linked AI summary

Manifold Elastic Net: A Unified Framework for Sparse Dimension Reduction

Tianyi Zhou, Dacheng Tao, Xindong Wu

arXiv:1007.3564v3cs.LGstat.ML

TL;DR

Sparse manifold-learning dimensionality reduction is difficult to optimize with standard LARS because its penalized objective is not directly a lasso least-squares problem. MEN reformulates the objective so LARS can obtain a sparse solution, and face-recognition experiments report better, more stable performance than popular alternatives.

  • Problem

    Existing sparse manifold dimensionality-reduction objectives are not directly lasso-penalized least-squares problems, limiting straightforward use of LARS.

  • Method

    MEN applies an elastic net penalty to a discriminative manifold-learning loss and transforms the objective into a lasso-penalized least-squares problem for LARS optimization.

  • Results

    Face recognition on UMIST, FERET, and YALE shows better and more stable MEN performance than PCA, FLDA, DLA, supervised LPP, supervised NPE, and SPCA.

  • Takeaways & Limitations

    MEN combines local-geometry preservation, discriminative criteria, sparse computation, reduced over-fitting, and interpretable projection matrices for subsequent classification.

  • Takeaways & Limitations

    The paper leaves error-bound analysis, optimal sparsity selection, and replacing lasso with alternatives such as ℓ0-norm or SCAD for future work.

Abstract

from arXiv · show

It is difficult to find the optimal sparse solution of a manifold learning based dimensionality reduction algorithm. The lasso or the elastic net penalized manifold learning based dimensionality reduction is not directly a lasso penalized least square problem and thus the least angle regression (LARS) (Efron et al. \cite{LARS}), one of the most popular algorithms in sparse learning, cannot be applied. Therefore, most current approaches take indirect ways or have strict settings, which can be inconvenient for applications. In this paper, we proposed the manifold elastic net or MEN for short. MEN incorporates the merits of both the manifold learning based dimensionality reduction and the sparse learning based dimensionality reduction. By using a series of equivalent transformations, we show MEN is equivalent to the lasso penalized least square problem and thus LARS is adopted to obtain the optimal sparse solution of MEN. In particular, MEN has the following advantages for subsequent classification: 1) the local geometry of samples is well preserved for low dimensional data representation, 2) both the margin maximization and the classification error minimization are considered for sparse projection calculation, 3) the projection matrix of MEN improves the parsimony in computation, 4) the elastic net penalty reduces the over-fitting problem, and 5) the projection matrix of MEN can be interpreted psychologically and physiologically. Experimental evidence on face recognition over various popular datasets suggests that MEN is superior to top level dimensionality reduction algorithms.

1 Introduction

The paper motivates MEN as a way to combine manifold structure, discriminative information, and sparse representation while enabling LARS-based optimization. It applies this framework to subsequent classification and reports favorable face-recognition results.

  • Motivation: Sparse dimensionality reduction can improve computational parsimony, generalization, and model interpretability.Sparsity simplifies low-dimensional representation and subsequent processing, can reduce over-fitting variance, and supports interpretation.
  • Optimization: Equivalent linear-algebra transformations rewrite MEN as a lasso-penalized least-squares problem, allowing LARS to obtain its optimal sparse solution.This transformation addresses the fact that the original manifold-learning objective is not directly a lasso least-squares problem.
  • Limitations of prior work: Existing sparse dimensionality-reduction methods largely target regression, while classification-oriented methods may discard labels or be limited to binary classification.SPCA ignores class labels, SLDA is restricted to binary classification, and other approaches have constrained settings.
  • Proposed approach: MEN applies an elastic net penalty to a discriminative manifold-learning loss to obtain a sparse projection matrix for subsequent classification.The framework is designed to preserve manifold-learning advantages while incorporating sparse learning.
  • Optimization: The MEN implementation uses an active-set LARS procedure whose loop count controls projection sparsity.The algorithm outputs a sparse projection matrix, and smaller K induces a sparser matrix.

2 Manifold Elastic Net

The paper frames MEN as a general sparse solution for discriminative manifold dimensionality reduction. It addresses limitations of manifold and sparse methods by combining local-structure preservation with classification-oriented optimization and elastic-net regularization.

  • Problem setting: Manifold dimensionality reduction preserves intrinsic structure but may not explicitly minimize classification error or produce interpretable feature representations.Its low-dimensional coordinates can linearly combine all high-dimensional variables.
  • Problem setting: Sparse learning improves computational parsimony, discourages over-fitting, and supports interpretation, but existing methods often ignore intrinsic data structure.The cited sparse methods are primarily designed for linear regression.
  • Framework: MEN is a general framework for sparse discriminative manifold dimensionality reduction and subsequent classification.It is presented as a way to obtain sparse solutions while retaining manifold-learning and sparse-learning benefits.
  • Framework: MEN uses the patch alignment framework and a classification-error-minimization criterion rather than simply combining existing manifold and sparse algorithms.It encodes local geometry, aligns coordinates, and links the representation to classification error.

2.1 Part optimization

MEN constructs local patches around each training sample and optimizes their low-dimensional representations to preserve local geometry while separating classes. A trade-off parameter balances within-class similarity against between-class separation.

  • Patch construction: Each patch contains a sample and related neighbors, with separate groups drawn from the same and different classes.The groups contain k1 same-class neighbors and k2 different-class neighbors.
  • Local geometry: MEN maps each high-dimensional patch to a low-dimensional patch and maximizes preservation of the patch’s local geometry.The local-geometry encoding matrix Li varies with the dimensionality-reduction algorithm.
  • Discriminative optimization: The part optimization seeks small distances to related same-class samples and large distances to related different-class samples.This objective combines local geometry with discriminative separation in the low-dimensional subspace.
  • Discriminative optimization: κ controls the relative influence of the two parts of the local optimization.The coefficient vector and resulting part-optimization matrix are then constructed from this objective.

2.2 Whole alignment

After optimizing individual patches, MEN aligns their low-dimensional representations into a consistent global coordinate system. It then adopts a linear approximation and forms an objective with tunable trade-offs before sparse regularization.

  • Global alignment: Each patch has a corresponding low-dimensional representation that is selected from a shared global coordinate system.Selection matrices identify the coordinates associated with individual patches.
  • Global alignment: Summing the part optimizations over all patches produces the whole-alignment objective.The resulting alignment matrix L is obtained through an iterative procedure.
  • Linear approximation: MEN approximates the potentially nonlinear mapping from high-dimensional samples to low-dimensional coordinates with the linear relation Z = XW.The objective minimizes the difference between the aligned representation Z and its linear approximation XW.
  • Objective construction: Trade-off parameters α and β control the influence of different components of the MEN objective.These parameters are introduced after constructing the linear approximation objective.

2.3 Classification error minimization

This section incorporates classification error minimization into MEN and designs a flexible indicator matrix so the selected subspace can have any dimension from 1 to c −1.

  • MEN considers discriminative information for classification, but its initial objective does not directly model classification error.
  • Applying least square error minimization is a usual approach for binary classification problems.
  • Multi-class classification is challenging because the class label vector C cannot be directly used as the regression response Y.
  • LS-LDA links least-square formulation with conventional LDA under a mild condition but restricts the reduced subspace to c −1 dimensions.
  • MEN flexibly designs the indicator matrix Y, allowing any selected subspace dimension between 1 and c −1 for lower-dimensional representation and recognition applications.
  • For nearest-neighbor classification, projecting same-class samples to their class center while maximizing center variance motivates weighted PCA of class centers.

2.4 Elastic net penalty

MEN combines l1 and l2 penalties to obtain sparse projections while retaining elastic-net grouping benefits and avoiding limitations of the lasso penalty.

  • The l0 penalty can characterize nonzero projection entries, but imposing it makes the optimization problem NP-hard.
  • LARS greedily searches the optimal solution path for lasso-penalized linear regression while shrinking coefficients toward zero and preserving prediction accuracy.
  • Lasso selects at most as many variables as observations and may select only one variable from a correlated group.
  • Adding an l2 penalty increases projection rank and provides the elastic-net grouping effect alongside the l1 penalty.
  • MEN adds both l1-norm and l2-norm penalties to its objective to produce a sparse projection matrix with grouping behavior.

2.5 LARS for MEN

Although MEN is not initially written as penalized least squares, equivalent transformations convert it into a form solvable by LARS, which constructs sparse projection columns iteratively.

  • The MEN objective is not directly a penalized least-square problem, so LARS cannot be applied to its original form.
  • Independent projection-matrix columns allow LARS to solve MEN one column at a time using corresponding indicator-matrix vectors.
  • Eliminating the low-dimensional representation Z reduces MEN to an objective expressed in the projection matrix W.
  • The transformed objective uses an asymmetric matrix computed from the alignment matrix and an eigenvalue decomposition to obtain a quadratic form.
  • LARS begins with zero coefficients, adds the most correlated feature to the active set, and moves coefficients along an equiangular direction.
  • Active-set sparsity is controlled by the number of nonzero coefficients, while active variables share equal correlations exceeding those of inactive variables.
  • Each loop adds one variable, computes the coefficient direction and step distance, and produces a K-sparse transformed coefficient vector after K loops.
  • The step distance is limited by either an inactive variable reaching the active correlation or an active coefficient reaching zero.

2.6 Fast LARS

Fast LARS reduces the cost of repeatedly inverting the growing active-set Gram matrix by updating its inverse incrementally and exploiting sparse structure.

  • LARS becomes inefficient for large training sets because computing the growing Gram-matrix inverse is costly.
  • Block matrix calculations update the kth inverse from the inverse computed in the previous loop after adding a new active-set variable.
  • The inverse-calculation cost decreases from O(p3) to O(p2 + 5p) when the previous-loop inverse is available.
  • Fast LARS can further reduce computation by exploiting the sparse structure of X∗ in equiangular-vector and inner-product calculations.

2.7 Algorithm

MEN constructs a sparse projection through manifold geometry, discriminative information, and column-wise LARS optimization. The resulting matrix projects samples into a low-dimensional K-sparse subspace with stated computational efficiency.

  • Algorithm inputs and initialization: MEN initializes training data and class labels, then optionally reconstructs the data with PCA before manifold and classification-error processing.The algorithm takes X, class labels C, subspace dimension d, and loop count K as inputs.
  • Manifold construction: Local patches are optimized separately, aligned into a global matrix L, and combined to retain the dataset's manifold structure.Patch matrices Li are computed for each sample and unified through whole alignment.
  • Discriminative processing: A weighted-PCA procedure over class centers computes indicator matrix Y for classification-error minimization.MEN then derives new matrices X∗ and Y∗ from X and Y.
  • Sparse optimization: LARS updates the active set, direction, distance, and coefficients for each projection column until K variables have been selected.The projection matrix is built column by column, with an incremental Gram-matrix inverse used to speed LARS.
  • Computational output: For p ≫ n, MEN requires O(dK3 + dpK2) operations to obtain a d-column projection with K nonzero elements per column.The stated cost reflects d LARS runs and simple matrix computations in most LARS steps.

2.8 Discussions

The discussion presents MEN as a unified manifold-and-sparse framework and establishes the theoretical basis for solving it with LARS. It argues convergence through equivalence to a generalized lasso-regularized problem, monotonicity, and boundedness.

  • Framework rationale: MEN embeds manifold learning and sparse learning complementarily, retaining local geometry while using weighted lasso and ℓ2 penalties to produce grouped sparse projections.The combined lasso and ℓ2 penalties are termed the elastic net.
  • Problem equivalence: LARS is applicable because MEN is a special case of a generalized lasso-regularized problem that LARS can solve.The generalized formulation allows an asymmetric square matrix A and constants B, C, and t.
  • Equivalent formulation: The proof transforms the generalized objective into a lasso-regularized least-square problem, ignoring constants after decomposing its quadratic term.The cited derivation introduces an eigenvalue decomposition before the transformation.
  • Convergence result: LARS converges because the objective is monotonic during optimization and bounded.The theorem explicitly states convergence for the problem defined in Eq.39.
  • Datasets: Figure 1 displays sample face images from UMIST, FERET, and YALE in rows ordered by database.The first, second, and third rows correspond to UMIST, FERET, and YALE, respectively.

3 Experiments

The experiments evaluate MEN against six dimensionality-reduction algorithms on UMIST, FERET, and YALE face datasets using recognition rates across subspace dimensions. MEN consistently performs strongly, particularly in low-dimensional settings, while sparsity supports robustness, interpretability, and lower computational cost.

  • Experimental setup: MEN is compared with PCA, FLDA, DLA, SLPP, NPE, and SPCA on the UMIST, FERET, and YALE face datasets.The experiments use standard face-image databases and evaluate discriminative dimensionality reduction.
  • Experimental setup: Recognition rates are evaluated after randomly splitting each dataset into training and testing sets, learning a projection from training data, and classifying projected test samples with nearest neighbors.Experiments use 5 or 7 training images per person on UMIST and YALE, 4 or 5 on FERET, and repeat each setting five times.
  • Recognition results: MEN consistently outperforms the other six algorithms on UMIST and outperforms them on YALE, retaining high recognition rates when the selected subspace is low-dimensional.On YALE, the MEN curves are also smoother, which the paper interprets as greater stability.
  • Recognition results: Sparse methods such as MEN and SPCA reach their best recognition rates in lower-dimensional subspaces, while SPCA performs worse than supervised methods because it does not use class labels.The paper attributes the lower-dimensional performance to lasso-based selection of significant features.
  • Robustness and interpretation: MEN achieves the most robust recognition rates in the boxplots, combining sparsity, local intra-class geometry, and inter-class margin and classification-error criteria.The paper also reports that manifold and discriminant methods are more stable than PCA and SPCA because they use class-label information.
  • Robustness and interpretation: MEN’s sparse projection bases contain less noise than PCA and DLA bases, and selected features correspond to recognizable facial regions such as ears, nose, eyes, and mouth.The sparse projection matrix is reported to improve interpretability and reduce subsequent computational cost relative to dense matrices.

4 Conclusion

MEN provides a unified sparse projection framework that combines discriminative manifold learning with elastic-net regularization and can be solved through LARS after equivalent transformations. Experiments on face-recognition datasets indicate better and more stable performance than popular dimensionality-reduction methods, while several theoretical and sparsity-selection questions remain open.

  • Framework: MEN imposes an elastic-net penalty on a patch-alignment-based loss to obtain a sparse projection matrix for subsequent classification.The framework combines manifold-learning and sparse-learning dimensionality reduction without directly combining the two methods.
  • Optimization: Equivalent linear-algebra transformations rewrite MEN as a lasso-penalized least-squares problem, enabling LARS to obtain its optimal sparse solution.MEN is optimized through a lasso-type regression formulation after the transformations.
  • Advantages: MEN preserves local intra-class geometry, incorporates margin maximization and classification-error minimization, improves computational parsimony, reduces over-fitting, and supports psychological and physiological interpretation.These properties are presented as advantages for subsequent classification.
  • Experiments: Face-recognition experiments on UMIST, FERET, and YALE show that MEN performs better and more stably than popular dimensionality-reduction algorithms.The comparisons include PCA, FLDA, DLA, supervised LPP, supervised NPE, and SPCA.
  • Limitations and future work: The paper leaves MEN's error bounds, optimal sparsity selection, and possible replacements for lasso insufficiently developed for future work.Suggested directions include compressed sensing, ℓ0-norm penalties, SCAD, reweighted ℓ1 minimization, adaptive lasso, and adaptive elastic net.
Loading 1007.3564v3…