4 ms·

I don't know Python, so I may be missing something, but: I don't understand how the naive approach can be O(n^2) if it involves matrix multiplication. Surely

I don't know Python, so I may be missing something, but: I don't understand how the naive approach can be O(n^2) if it involves matrix multiplication. Surely at best it would be somewhere between O(n^2) and O(n^3), and most likely O(n^3)?

alexchamberlain 13y ago
There's no matrix multiplication, just vector dot product. (Yes, you can express it as a matrix multiplication, but nurrrr)
- weland 13y ago
  I don't think I've seen the dot product there. Don't just throw terms around, it's very confusing for beginners :-). While I may have missed your idea about the dot product, I'm quite sure you can't express a dot product as a matrix multiplication; perhaps you were thinking you can express matrix multiplication in terms of dot products, but I don't see how that answer's OP's question.
  - dbaupp 13y ago
    A conventional (i.e. with vectors over ℝ) dot product is just a matrix multiplication between a 1×n and an n×1 matrix.
    - weland 13y ago
      That hardly qualifies as "you can express dot product as matrix multiplication" in the context of the discussion about complexity. I also think it's backwards from a theoretical standpoint. Dot product isn't a cornercase of matrix multiplication, it has a meaning of its own that can be viewed without even introducing matrices. You can view matrix multiplication as computationally equivalent with a sequence of dot products, but that where stuff ends; otherwise, for instance, matrix multiplication also doesn't have all the properties that the dot product has (e.g. it's not commutative). I know a lot of books take this shortcut, but the two concepts are different enough that, IMO, they do not warrant alexchamberlain's remark.
  - alexchamberlain 13y ago
    In all fairness, I misread the article. However, dot product is a very basic mathematical concept all readers of Hacker News should be aware of. Again, expressing the dot product as a matrix multiplication is basic linear algebra.
sampo 13y ago
The post means matrix-vector multiplication, which is O(n^2). You're thinking of matrix-matrix multiplication, for which the naive algorithm is O(n^3). He writes X⃗ = M⋅x⃗ and here only M is a matrix. x⃗ is a vector and X⃗ is the discrete fourier transform of it, also a vector.
- benjamincburns 13y ago
  Total tangent, but man do I love unicode! Also for future reference, there's a superscript two (² at U+00B2) and three (³ at U+00B3).
  - Dylan16807 13y ago
    Bah, those two are firmly in 8859-1 territory.

alexchamberlain 13y ago

There's no matrix multiplication, just vector dot product. (Yes, you can express it as a matrix multiplication, but nurrrr)

weland 13y ago
I don't think I've seen the dot product there. Don't just throw terms around, it's very confusing for beginners :-). While I may have missed your idea about the dot product, I'm quite sure you can't express a dot product as a matrix multiplication; perhaps you were thinking you can express matrix multiplication in terms of dot products, but I don't see how that answer's OP's question.
- dbaupp 13y ago
  A conventional (i.e. with vectors over ℝ) dot product is just a matrix multiplication between a 1×n and an n×1 matrix.
  - weland 13y ago
    That hardly qualifies as "you can express dot product as matrix multiplication" in the context of the discussion about complexity. I also think it's backwards from a theoretical standpoint. Dot product isn't a cornercase of matrix multiplication, it has a meaning of its own that can be viewed without even introducing matrices. You can view matrix multiplication as computationally equivalent with a sequence of dot products, but that where stuff ends; otherwise, for instance, matrix multiplication also doesn't have all the properties that the dot product has (e.g. it's not commutative). I know a lot of books take this shortcut, but the two concepts are different enough that, IMO, they do not warrant alexchamberlain's remark.
- alexchamberlain 13y ago
  In all fairness, I misread the article. However, dot product is a very basic mathematical concept all readers of Hacker News should be aware of. Again, expressing the dot product as a matrix multiplication is basic linear algebra.

sampo 13y ago

The post means matrix-vector multiplication, which is O(n^2). You're thinking of matrix-matrix multiplication, for which the naive algorithm is O(n^3). He writes X⃗ = M⋅x⃗ and here only M is a matrix. x⃗ is a vector and X⃗ is the discrete fourier transform of it, also a vector.

benjamincburns 13y ago
Total tangent, but man do I love unicode! Also for future reference, there's a superscript two (² at U+00B2) and three (³ at U+00B3).
- Dylan16807 13y ago
  Bah, those two are firmly in 8859-1 territory.