search

rluce / tlcomp

Computing with Toeplitz and Toeplitz-like matrices in Matlab
MIT License
1 stars 0 forks source link

Add O(n^2) time and O(n) space implementation of 1, inf, fro norm #8

Closed rluce closed 6 years ago

rluce commented 6 years ago

For |TLMat| and |ToepMat| the matrix 1/inf/fro norms can simply computed in O(n^2) by

norm(full(T), p).

Note that this is done in O(n^2) space. This can easily be brought down to O(n) space and O(n) time for |ToepMat|. For |TLMat|, these operations can be implemented in O(n) space as follows. The columns of T are generated one-after-one in toeplkreconstruct, and once they are accounted for in the norm computation, they can be discarded.

rluce commented 6 years ago

Basic support is finished with commit 8c7f9da.

For TLMat it would be interesting to investigate whether the norms can be computed in O(dn) instead of O(dn^2). A starting point would be the sum_1^d circulant(x_j)*circulant(y_j) representation of T.