# Computational complexity for linear discriminant analysis

The linear discriminant analysis algorithm is as follows: I want to conduct a computational complexity for it. For each step, the complexity is as follows:

1. For each $c$, there are $N_cd$ additions and $1$ division. Thus, in total, there are $Nd+C$ operations.
2. $Nd$ additions and $1$. Thus, in total, there are $(Nd+1)$ operations.
3. There are $N(d+d^2)$, the first $d$ is for $x_j-m_c$, and the second $d^2$ is for ${(x_j-m_c)}{(x_j-m_c)}^T$.
4. There are $C(d+d^2+d^2)$, the first $d$ is for $m_c-m$, the second $d^2$ is for ${(m_c-m)}{(m_c-m)}^T$, and the third $d^2$ is for the multiplication between $N_c$ and the matrix.
5. There are $d^3+d^3+d^3$, the first $d^3$ is for ${S_w}^{-1}$ and the second $d^3$ is for the multiplication between ${S_w}^{-1}$ and $S_b$, and the third $d^3$ is for the eigen-decomposition.

In general, we have $N>d>C$, thus the dominated term is $Nd^2$. To sum up, the computational time complexity is $O(Nd^2)$.

My question is: is the analysis right? If not, please help correct it. I have this question because I've read some papers on this subject, but there are different results among them. Any comments would be highly appreciated.

• What's about the complexity of the asymmetric eigen-problem (point 5)? I think that this question is not statistical and would better go to a computer science forum. – ttnphns Mar 20 '15 at 6:44
• Are you sure that it is symmetric? For all that I know it is not (see LDA algo in footnote 1). – ttnphns Mar 20 '15 at 7:04
• I'm a little surprised at the close votes--this seems like a pretty reasonable question for Cross Validated, though it'd probably be on topic at CS too.... – Matt Krause Mar 21 '15 at 1:21
• Just FYI, people generally don't like cross-posting the same question to multiple sites (at least, not right away). If you want to move it to CS, I think a mod can make that happen for you. – Matt Krause Mar 21 '15 at 3:23
• For general (i.e. k-class, also called "canonical") LDA algorithm please see stats.stackexchange.com/a/48859/3277 and further links there. – ttnphns Jan 11 '18 at 17:12

## 1 Answer

There are two potential bottlenecks:

1. As you pointed out, finding the within-class scatter in step 3 takes $N(d+d^2)$ steps, or $O(Nd^2)$.

2. Both the matrix multiplication and eigendecomposition in step 5 take approximately $O(d^3)$. Depending on the algorithm, matrix multiplication can be a bit faster: there are algorirthms that are $\sim O(n^{2.4})$ and you can also cheat a bit because you don't need to compute every single eigenvector.

The other steps are relatively trivial, so your answer depends on whether $N>d$. If you have more features than examples, it's $O(d^3)$, otherwise it's $O(Nd^2)$

This paper by Cai, He, and Han walks through the space/time complexity in more detail. Annoyingly, they use $m$ to mean the number of examples, which you called $N$, while using $N$ to refer to the number of features, which you call $d$, so beware.

The paper also shows a related algorithm that is more time and space efficient.

• Hi, @MattKrause, thank you very much for affirming this description. In fact, I've read Cai's paper that you referenced. Because they proposed a speeding algorithm for LDA, there are some steps that are different from the steps I posted. They also discussed the cases $m>n$ and $m<n$, where there are different processing procedure for more efficiency and economical storage. I have this question because I want to confirm myself that the algorithm analysis posted above is right. Thank you! – mining Mar 21 '15 at 4:28