solde_tr: Stable and Orthogonal Local Discriminant Embedding using...

In bbuchsbaum/discursive: What the Package Does (One Line, Title Case)

Stable and Orthogonal Local Discriminant Embedding using Trace Ratio Criterion (SOLDE-TR) with nanoflann-based k-NN for Fast Adjacency Construction

Description

This is an extension of the SOLDE-TR algorithm described in: \insertRefyang2017stable

The method extends the Stable Orthogonal Local Discriminant Embedding (SOLDE) approach by recasting its objective function into a trace ratio optimization problem and using an iterative trace-ratio (ITR) algorithm to jointly learn the orthogonal projection vectors. Compared to the step-by-step SOLDE, SOLDE-TR converges faster, yields a global solution, and usually provides improved performance in tasks such as face recognition.

What is new in this version? We accelerate the adjacency graph construction (Steps 1–2 in Section 3 of the paper) by using the Rnanoflann package, which provides a nanoflann-backed kd-tree for extremely fast nearest neighbor (k-NN) queries. This can be a substantial improvement over naive O(N^2) neighbor searches when N is large.

Correspondence to the Paper Sections:

• Equations (1), (2), (3): Construction of adjacency (weight) matrices S, H, F for similarity, diversity, and inter-class separability.

• Equations (4)–(6): Objective functions in local discriminant embedding.

• Equation (7): Combination into L_d = \alpha L_s - (1-\alpha)L_v.

• Equations (11)–(16): The trace ratio formulation and iterative algorithm.

Usage

solde_tr(
  X,
  y,
  s = 5,
  alpha = 0.9,
  sigma = 1,
  m = 10,
  tol = 1e-06,
  maxit = 100,
  pca_preprocess = TRUE
)

Arguments

X	A numeric matrix of size N \times D (row-wise samples).
y	A numeric vector of length N (class labels).
s	Number of neighbors for adjacency; default = 5.
alpha	Numeric in [0.5, 1]. Balances L_s vs L_v in L_d = alpha * L_s - (1-alpha)*L_v; default = 0.9.
sigma	Positive scalar for the heat kernel \(\exp(-\|x_i - x_j\|^2 / \sigma)\); default = 1.0.
m	Desired dimension of the subspace; default = 10.
tol	Stopping threshold for change in trace ratio; default = 1e-6.
maxit	Maximum number of ITR iterations; default = 100.
pca_preprocess	Logical: whether to do PCA to ensure full rank; default = TRUE.

Details

Main steps:

1. (Optional) PCA Projection: We project X into a PCA subspace to ensure S_d is nonsingular.

2. Build Adjacency Graphs with Rnanoflann: - S (similarity) If two points x_i and x_j belong to the same class and either x_j is among the s nearest neighbors of x_i or x_i is among the s neighbors of x_j, then S_{ij} = \exp(-\|x_i - x_j\|^2/\sigma). - H (diversity) Same condition (same-class neighbors), but H_{ij} = 1 - \exp(-\|x_i - x_j\|^2/\sigma). - F (interclass) If x_i and x_j are from different classes and they are in each other's s neighborhoods (union condition), then F_{ij} = \exp(-\|x_i - x_j\|^2/\sigma).

   We implement this neighbor search using \code{nanoflann}'s kd-tree via \code{nn()} from
   the \pkg{Rnanoflann} package for Euclidean distance.
   

3. Iterative Trace Ratio (ITR): Solve

   \max_{W^T W = I} \frac{\mathrm{tr}(W^T S_p W)}{\mathrm{tr}(W^T S_d W)},

   with S_p = X L_m X^T and S_d = X L_d X^T, via the iterative approach: \mathbf{M} = \mathbf{S_p} - \lambda \mathbf{S_d}, eigen-decompose \(\mathbfM\), pick the top m eigenvectors. Update \(\lambda\), repeat until convergence.

4. Final Embedding: \mathbf{W} = \mathbf{W}_{\mathrm{PCA}} \times \mathbf{W}_{\mathrm{SOLDE-TR}}.

Value

A list with:

W_pca	The PCA projection matrix (columns are the top PCA components).
W_solde_tr	The m projection vectors from the trace ratio solution in the PCA subspace.
W	The final D x m projection matrix = \(\mathbfW\mathrmPCA \times \mathbfW\mathrmSOLDE-TR\).
eigvals_pca	Eigenvalues of the PCA step (if pca_preprocess = TRUE).
trace_ratio_history	Vector of trace ratio values across ITR iterations.

References

1. Yang, X., Liu, G., Yu, Q., & Wang, R. (2017). Stable and orthogonal local discriminant embedding using trace ratio criterion for dimensionality reduction. Pattern Recognition, 71, 249–264.

2. Wang, J., Zhu, X., & Gong, S. (2007). ITR: Iterative trace ratio algorithm for feature extraction. IEEE Transactions on Knowledge and Data Engineering.

3. He, X., Yan, S., Hu, Y., Niyogi, P., & Zhang, H. (2005). Face recognition using Laplacianfaces. IEEE Trans. on Pattern Analysis and Machine Intelligence.

4. Rnanoflann https://github.com/ManosPapadakis95/Rnanoflann

Examples

## Not run: 
 # Simple test on a small dataset
 library(Rnanoflann)
 set.seed(1)
 N <- 100
 D <- 20
 X <- matrix(rnorm(N*D), nrow = N, ncol = D)
 y <- sample.int(3, size = N, replace = TRUE)

 solde_res <- SOLDE_TR_fastNN(X, y, s=5, alpha=0.9, sigma=1.0, m=8, tol=1e-5, maxit=50)
 # Project new data X_new:
 # Ynew <- t(solde_res$W) %*% t(X_new)

## End(Not run)

bbuchsbaum/discursive documentation built on April 14, 2025, 4:57 p.m.