# How does linear discriminant analysis reduce the dimensions?

There are words from "The Elements of Statistical Learning" on page 91:

The K centroids in p-dimensional input space span at most K-1 dimensional subspace, and if p is much larger than K, this will be a considerable drop in dimension.

I have two questions:

1. Why the K centroids in p-dimensional input space span at most K-1 dimensional subspace?
2. How are the K centroids located?

There is no explain in the book and I didn't find the answer from related papers.

• The $K$ centroids lie in an at most $K-1$ dimensional affine subspace. For example, two points lie on a line, a $2-1$ dimensional subspace. This is just the definition of an affine subspace and some elementary linear algebra. Feb 15, 2012 at 12:56
• A very similar question: stats.stackexchange.com/q/169436/3277. Aug 31, 2015 at 12:24

Discriminants are the axes and the latent variables which differentiate the classes most strongly. Number of possible discriminants is $$min(k-1,p)$$. For example, with k=3 classes in p=2 dimensional space there can exist at most 2 discriminants such as on the graph below. (Note that discriminants are not necessarily orthogonal as axes when drawn in the original space, although they, as variables, are uncorrelated.) The centroids of the classes are located within the discriminant subspace according to the their perpendicular coordinates onto the discriminants. Algebra of LDA at the extraction phase is here.

Also on plotting a discriminant.

The data on the plot above:

 cluster    v1       v2
(class)
1   5.9808   5.9060
1   6.4567   5.8481
1   5.4387   6.0338
1   5.5606   5.9366
1   5.8649   5.9948
1   5.1921   6.2982
1   5.1004   6.0873
1   6.3185   6.1709
1   6.4845   5.8965
1   6.3065   5.9778
1   5.9209   6.2031
1   5.3548   5.5192
1   5.8433   5.9944
1   6.6250   6.0908
1   6.2428   5.7777
1   5.7597   6.1269
1   5.9403   5.7705
1   4.6054   5.7073
1   5.6858   5.9476
1   6.1778   5.6111
1   6.3430   5.7566
1   5.6905   6.0274
1   5.6846   5.9551
1   5.5760   5.7143
1   5.3941   5.7118
1   5.4967   6.4571
1   5.8920   5.6266
1   5.9580   6.1780
1   6.8785   6.1241
1   6.0701   6.0319
1   5.9133   5.9849
1   6.2660   6.2809
1   5.2253   5.8921
1   5.2506   5.8159
1   5.8415   6.0320
1   5.0210   5.6914
1   6.1382   6.2279
1   6.1128   6.1827
1   5.5793   5.9129
1   5.8707   5.7803
1   6.5149   6.2894
1   5.1673   5.6199
1   6.4698   6.0972
1   5.7219   5.8623
1   5.5785   5.8486
1   6.9186   5.9136
1   5.6157   5.8057
1   5.6855   5.7513
1   5.6458   5.9635
1   6.0314   5.9153
2   5.1039   4.1146
2   4.4599   4.3446
2   4.9609   3.4868
2   3.9257   3.8578
2   4.3205   3.7520
2   4.8456   4.6628
2   4.5335   4.2763
2   4.5852   4.1707
2   4.3019   5.1531
2   4.8491   3.7221
2   4.2041   3.8910
2   3.6117   4.0363
2   4.4916   4.0226
2   4.6444   3.8739
2   4.2410   4.5151
2   4.9834   3.7917
2   4.0926   4.2093
2   4.7622   4.1137
2   5.0233   3.7018
2   4.5019   4.0136
2   4.0822   4.2910
2   4.4028   3.8086
2   4.1417   3.6089
2   5.1602   3.5025
2   4.6337   4.3815
2   4.3084   4.0749
2   4.1309   4.0167
2   4.2047   4.3202
2   4.9091   3.6691
2   4.4928   3.9364
2   4.6608   4.5434
2   4.3573   4.1845
2   4.2845   3.8381
2   5.6341   3.5013
2   4.3335   4.2123
2   4.2251   4.4540
2   4.8490   4.4981
2   5.0219   3.8409
2   4.4754   4.4494
2   4.8051   4.0189
2   4.6656   3.6700
2   4.6717   3.6381
2   4.5191   3.6215
2   4.5762   4.1979
2   4.2370   4.5322
2   4.5737   3.9564
2   3.7806   4.0168
2   4.8040   3.8413
2   4.1680   4.1957
2   4.8557   4.0310
3   3.9832   5.6590
3   3.5904   5.1865
3   4.0862   4.6412
3   4.1941   4.9218
3   3.5012   5.6206
3   3.4428   6.0566
3   3.5920   5.4389
3   4.8300   5.4171
3   3.9986   4.8301
3   3.3671   5.4289
3   3.6288   5.1387
3   3.6887   5.0804
3   3.1191   5.4220
3   4.2507   5.1695
3   4.5849   4.6248
3   4.1990   5.4435
3   3.8047   5.7231
3   3.9704   5.4122
3   4.0506   5.2519
3   4.0900   4.8446
3   3.9979   4.6423
3   4.3036   4.8175
3   4.4082   5.4607
3   4.5216   4.8039
3   4.4300   4.1941
3   3.7606   5.6208
3   3.7228   5.0587
3   4.0865   5.8328
3   3.3511   5.2844
3   4.3555   4.4605
3   4.2938   5.4642
3   3.6316   4.7933
3   3.5885   5.2833
3   4.3816   4.8879
3   4.3523   4.9524
3   4.0294   4.9552
3   4.2613   5.3241
3   4.0465   5.4570
3   4.4261   5.4266
3   3.4056   5.2845
3   4.9786   4.7297
3   4.0736   5.2606
3   4.0491   4.8352
3   3.2578   4.9190
3   4.2572   5.2376
3   3.8958   4.7273
3   3.2073   5.4326
3   3.5651   5.0515
3   4.0246   5.1731
3   3.7964   4.9051


Covariances:

CLASS 1
.2349394555   .0284715802
.0284715802   .0418875212
CLASS 2
.1437793718  -.0421373789
-.0421373789   .1178458544
CLASS 3
.1756961817  -.0544151176
-.0544151176   .1401276825
POOLED
.1848050030  -.0226936388
-.0226936388   .0999536861
TOTAL
.8074294595 .3558593873
.3558593873 .7068285731


Excerpt from LDA results:

Eigenvalues of the discriminant functions:
9.3968
1.4438

Eigenvectors of the discriminant functions (column-normalized to SS=1):
dis1     dis2
v1    .4758    .7502
v2    .8796   -.6612
(this is the oblique rotation matrix "variables into discriminants", exemplified by the plot)

SSCP(eigenvectors)
1.0000000   -.2246239
-.2246239   1.0000000
(-.2246239 = approx 103 degree angle b/w the discriminants on the plot)

• Nice graph, what software/package did you use to create it? Feb 15, 2012 at 18:18
• SPSS. Self-written macro for SPSS. Feb 15, 2012 at 18:53
• Does this mean that you won't see good class separation in an LDA with, say, three classes with overlap, until you rescale the axis?? I mean, I'm running an LDA, and my classes separate...but they are right on top of eachother in every discriminate axis except the first one...and that one is huge. Feb 10, 2016 at 22:26

While "The Elements of Statistical Learning" is a brilliant book, it requires a relatively high level of knowledge to get the most from it. There are many other resources on the web to help you to understand the topics in the book.

Lets take a very simple example of linear discriminant analysis where you want to group a set of two dimensional data points into K = 2 groups. The drop in dimensions will be only be K-1 = 2-1 = 1. As @deinst explained, the drop in dimensions can be explained with elementary geometry.

Two points in any dimension can be joined by a line, and a line is one dimensional. This is an example of a K-1 = 2-1 = 1 dimensional subspace.

Now, in this simple example, the set of data points will be scattered in two-dimensional space. The points will be represented by (x,y), so for example you could have data points such as (1,2), (2,1), (9,10), (13,13). Now, using linear discriminant analysis to create two groups A and B will result in the data points being classified as belonging to group A or to group B such that certain properties are satisfied. Linear discriminant analysis attempts to maximize the variance between the groups compared to the variance within the groups.

In other words, groups A and B will be far apart and contain data points that are close together. In this simple example, it is clear that the points will be grouped as follows. Group A = {(1,2), (2,1)} and Group B = {(9,10), (13,13)}.

Now, the centroids are calculated as the centroids of the groups of data points so

Centroid of group A = ((1+2)/2, (2+1)/2) = (1.5,1.5)

Centroid of group B = ((9+13)/2, (10+13)/2) = (11,11.5)


The Centroids are simply 2 points and they span a 1-dimensional line which joins them together. You can think of linear discriminant analysis as a projection of the data points on a line so that the two groups of data points are as "separated as possible"

If you had three groups (and say three dimensional data points) then you would get three centroids, simply three points, and three points in 3D space define a two dimensional plane. Again the rule K-1 = 3-1 = 2 dimensions.

I suggest you search the web for resources that will help explain and expand on the simple introduction I have given; for example http://www.music.mcgill.ca/~ich/classes/mumt611_07/classifiers/lda_theory.pdf

• Welcome to our site, Martino!
– whuber
Feb 15, 2012 at 15:00
• thanks @whuber, nice graph, I didn't have any such tools at hand :( Feb 15, 2012 at 15:14
• I didn't think you had the reputation to post an image anyway, Martino: that's why I made one for you. But now--or soon--you will have enough rep. If nothing is handy, you can use freely available software with geometric drawing capabilities like R or Geogebra. (You will find that illustrated replies get more attention: they are more attractive and readable.)
– whuber
Feb 15, 2012 at 15:19
• Why the downvote? If there's an issue with the answer it'd be helpful to point it out - I can't see one Oct 10, 2014 at 11:44