Localized Sliced Inverse Regression

by Qiang Wu, Sanyan Mukherjee and Feng Liang

Sliced inverse regression (SIR) for classification is equivalent to FDC. That is to solve a generalized eigenvalue problem Γβ=λΣβ, where Γ is the between-class covariance matrix and Σ is the total covariance matrix. The largest eigenvalues of this problem correspond to the disired directions. Well, in some cases we use the in-class covariance matrix B for Σ.

This has been discussed in Jieping Ye's paper extensively. In a way Σ is more likely to be non-singular than B. Due to the fact Σ = Γ + B, there exists a non-singular matrix A such that they can be diagonalized simultaneously with a transform Az = x. If they are non-singular, it matters not whether we use B or Σ. When B or Σ is singular, we might use its principal subspace or its null space for approximation (well it's not approximation I guess). I wonder what we shall do for SIR. Maybe we do the same rubbish too.

Now we come to the LSIR. The authors proposes a localized Γ by choosing the kNN samples of the same class. The only difference between LSIR and LFDC, I think, is the denominator part (i.e. a global covariance class v.s. a localized in-class covariance). Maybe I have to explore the corresponding graph to see their difference more clearly.

Their extension for SSL is to put all unlabelled samples into to all slices. That might be natural in the graph embedding framework. Why should I read this paper then?

Null Space versus Orthogonal Linear Discriminant Analysis

by Jieping Ye and Tao Xiong

In this paper, several LDA algorithms are addressed. The main result says OLDA and NLDA under certain conditions will yield the same result.

I seldom consider the details of the LDA algorithms, but after I read the journal version about the OLDA, I think it's necessary to get a summary for their current work. I am thinking about the possibility of reusing their techniques in the graph-based algorithms. But for the current paper, it's too far.

One deeply-sighted observation is the simultaneous diagonalization of S_w, S_b and S_t. Then the optimization is generalized from ``inverse'' of S_t to its pseudo-inverse. Actually, we have several constraints for different LDA algorithms. The ULDA requires orthogonality w.r.t. S_t while OLDA simply requires orthogonality w.r.t. an identity matrix. The so called NLDA maximizes the projected between class scatterness in the null space of S_w.

The condition they find for the equality is the rank equality. They test their algorithm on several high-dimensional data sets. I guess it's easy to follow their motivation.

Though lots of graph-based dimensionality reduction algorithms extensively use the idea from LDA, the simultaneous diagonalization is seldom feasible. Maybe, it's worth trying to get a more generalized solution for that rank-deficit general eigenvalue problem.

Local Fisher Discriminant Analysis for Supervised Dimensionality Reduction

by Masashi Sugiyama

I first knew this paper from afliboy, astonished since I was scanning ICML without scanning it first for my current research project. I am experimenting with it. However, up to now I still don't understand why it is not as good as I have expected on my data.

The idea is so simple. Everyone with experience in FDC will know it immediately. In FDC (or shall we say FDA in accordance with the author), we have two ``variance'' matrices, one for between-class (S_b), the other for within-class (S_w). The reduction is projecting samples into the eigen vectors of the generalized eigenvalue problem of (S_b, S_w), which is claimed to minimize the within-class variance and maximize the between-class variance simultaneously, for which I hold the belief that it is only one strategy for selecting a Pareto optimal (of coz, DNE uses another). The proposed idea reformulates the variance as

which allows us to think about the variance as a pairwise relationship, as if a graph, which I did several month ago without furthering the idea. If I had done, I would been more disappointed by now :-( So locality can be introduced by modifying the weights (those As).

Here As are the adjacent matrices. And this algorithm is then easy to kernelize, as FDC.

With several other papers on graph embedding, this area might be quite difficult to get new result. But anyway, let me try first.

Null Space versus Orthogonal Linear Discriminant Analysis

by Jieping Ye and Tao Xiong

This article tells me one important thing. LDA or Fisher discriminant criterion is still being studied by lots of guy. Last time I read one by Manli Zhu, in which they propose another different criterion than the traditional ones when the co-variance matrix is rank-deficient.

One of the simplest idea is applying a ridge purturbation to the singular with-in class covariance matrix, which is usu. called regularization. The other is finding an approximation in the principal subspace of S_w. Zhu's idea roots from the latter one, in which all principal directions are selected for later general eigenvalue problem. Zhu rejects those principal directions that are almost perpendicular to the subspace spanned by S_b.

In this paper, the author mentions several other strategies for dealing with the singularity of S_w, two of which they put attention to Orthognal LDA (OLDA) and Null Space LDA (NLDA). Their main result is they yield the same result under certain condtions. The condition is mild when dealing with high dimensional data (the number of dimension is much higher than the number of samples).

I guess I will review this article after I check those LDAs, which personally I suspect their usability. Here are those literatures:

• A new LDA-based face recognition system which can solve the small size problem, Pattern Recognition 33 (2000) by Chen and et al.
• Solving the small sample size problem of LDA, ICPR 2002, by Huang and et al.
• Characterization of a family of algorithms for generalized discriminant analysis on undersampled problems, JMLR 2005.
• Penalized discriminant analysis, Anals of Statistics 23 (1995) by Hastie and et al.