78
votes
Accepted
Why is uncomputability of the spectral decomposition not a problem?
The singular value decomposition, when applied to a real symmetric matrix $A = \sum_i \lambda_i(A) u_i(A) u_i(A)^T$, computes a stable mathematical object (spectral measure $\mu_A = \sum_i \delta_{\...
- 114k
41
votes
How fast can we *really* multiply matrices?
Recently there is a PhD thesis, Practical fast matrix multiplication algorithms, about the practical fast matrix multiplication algorithms like Strassen:
Matrix multiplication is a core building ...
- 511
23
votes
Why is uncomputability of the spectral decomposition not a problem?
The SVD decomposition falls under the family of phenomena where discontinuity implies non-computability. (Intuitively, this is because, at the point of discontinuity, infinite precision is required.)
...
- 48.8k
22
votes
Why is uncomputability of the spectral decomposition not a problem?
This is primarily an issue of backwards vs. forwards stability. Good SVD algorithms are backwards stable in the sense that the computed singular values and singular vectors are the true singular ...
- 1,160
20
votes
Why is fast matrix multiplication impractical?
Matrix multiplication based on Strassen's algorithm is in $O(n^{\log(7)/\log(2)})$ and is quite practical. As far as I am aware, for any
exponent $\omega<\log(7)/\log(2)$ the corresponding ...
- 13.1k
19
votes
Why is fast matrix multiplication impractical?
I acknowledge that the question concerns Boolean matrix multiplication.
However, a good deal of the opposition to fast matrix multiplication
algorithms is due to stability issues that can arise when ...
- 221
16
votes
Methods of solving linear system of equations, how to select the appropriate method
Disclaimer 1: Treating these topics properly would require a quick course in numerical analysis.
Disclaimer 2: If you are using any sane computer system, it's already going to have a library function ...
- 20.2k
10
votes
Decide if a matrix is transposable
There are polynomial-time reductions from your problem to Graph Isomorphism and vice-versa.
As a quick definition, when I speak of 'subdividing' an edge, I mean to replace each edge $u, v$ with a ...
- 12.4k
9
votes
Accepted
The singular values of the Hilbert matrix
I came back to this a few months ago and I can now answer my own question. I hope it is appropriate to answer my own question given the length of time.
Bernhard Beckermann and I just submitted a ...
- 3,217
9
votes
Accepted
Linear equations with absolute values
The problem is NP-hard over any field not of characteristic 2. We show this by reduction from an NP-complete NAE-3-SAT problem of checking satisfiability of a boolean formula $\land_{i} \mathrm{NAE}(...
- 5,590
9
votes
Accepted
Minimize spectral radius with orthogonal matrix
For an $n\times n$ matrix, the answer is
$$|\det A|^{\frac1n}.$$
Explanation: on the one hand, $\rho(UA)\ge|\det (UA)|^{\frac1n}=|\det A|^{\frac1n}$. On the other hand, singular value decomposition ...
- 52.3k
9
votes
Accepted
The eigenvalues of the matrix $\Big(\frac{1}{\cos(k-l)\frac{\pi}{n}}\Big)_{k,l=1}^n$
Here, we verify the observation of @BrendanMcKay that the eigenvalues are $n$ with multiplicity $(n+1)/2$ and $-n$ with multiplicity $(n-1)/2$.
Note that your matrix is skew-circulant, and it is known ...
- 656
8
votes
Solving a system of linear equations over the integers
To make sure I understand: you have an $m \times n$ matrix and vector in $\mathbb{Z}^n.$ Is the system a priori over- or under-determined? The former case is a little easier than the latter, but in ...
- 96.4k
8
votes
Accepted
Complexity of rectangular matrix multiplication
Assuming that efficient means better than the naive $O(n^{2+k})$ multiplication, let us review some possibilities.
Padding. For $k > \omega-2$, just pad $A$ with $n-n^k$ zero or garbage rows, ...
- 4,219
8
votes
Gaussian elimination is just Gram-Schmidt with a change to the inner product symbol?
I'm not sure how well this will answer the question "why does this happen?" But hopefully will provide more geometric/abstract views of this.
It seems to me that the Gram–Schmidt and ...
- 954
7
votes
Is this inequality involving the Frobenius norm right?
For a short fat matrix $G$ (more columns than rows), $\|AG\|_F \geq \sigma_{\min}(G)\|A\|_F \geq n \sigma_{\min}(G) \|A\|$, where $\sigma_{\min}(G)$ is the least singular value of $G$. This follows ...
- 20.2k
7
votes
Accepted
When are two binary matrices simultaneously equivalent to their transpose?
Clearly, a necessary condition is that for every word $w$ in two letters, one has
$${\rm Tr}\,w(A^t,B^t)={\rm Tr}\,w(A,B).$$
Equivalently,
$${\rm Tr}\,\hat w(A,B)={\rm Tr}\,w(A,B),$$
where $\hat w$ is ...
- 52.3k
7
votes
Is it faster to compute eigenvalues or coefficients of characteristic polynomials?
With the traditional algorithms and complexity measures used in numerical linear algebra (dense real matrices, floating point computations, flop count as a complexity measure), they are both more or ...
- 20.2k
7
votes
Why is fast matrix multiplication impractical?
Addressing the Boolean part.
Usually, fast matrix multiplication relies heavily on the element type being a ring; in particular, that every element has an additive inverse. For example, Strassen's ...
- 4,219
7
votes
Accepted
rank of an integer valued matrix
Note that if you take a prime $p$ and treat the matrix $A$ as a matrix $A'$ over $\mathbb{Z} / p \mathbb{Z}$, then from the property of $\operatorname{rank}(A)$ being the largest order of a non-zero ...
- 3,319
6
votes
Accepted
How can one construct a sparse null space basis using recursive LU decomposition?
On the LUQ decomposition
The algorithm implemented in luq (see reference given below) computes bases for the left/right null spaces of a sparse matrix $A$. ...
- 6,045
6
votes
Accepted
Spectrum of operator involving ladder operators
Q: Does anybody know how to numerically overcome this pseudospectral effect?
The key idea is "normal ordering". Rewrite the problem in such a way that annihilation operators $a$ appear to ...
- 188k
6
votes
Accepted
Usage and origin of the terms dictionary and atom in compressed sensing
The terms "dictionary" and "atoms" predate compressed sensing, they are more generally used in signal processing. An example is the Gabor atom for wavelets. For an early use of &...
- 188k
5
votes
Is this inequality involving the Frobenius norm right?
As stated$^*$ this problem has nothing to do with the Frobenius norm.
The map $T: A \mapsto AG$ is a linear transformation from a
finite-dimensional vector space, so for any norms we have
a constant $...
- 79.9k
5
votes
How can one construct a sparse null space basis using recursive LU decomposition?
Not the same algorithm, but here is an alternative that I have used in a recent paper; you can put it together quickly with standard Matlab functions if $A$ is a $m\times n$ matrix with $m\ll n$ (like ...
- 20.2k
5
votes
What is the time complexity of truncated SVD?
According to the man page of svds, provided by MATLAB, svds is currently based on "Augmented Lanczos Bidiagonalization Algorithm" when it comes to the top-$k$ SVD computation of a large-...
- 51
5
votes
Accepted
In a large sparse matrix, how many eigenvalues/eigenvectors are “spurious”?
Antisymmetric matrices are normal, hence they can be diagonalized with an orthogonal matrix. So $\|A\|_F^2=\sum |\lambda_i|^2$. If you keep only the $k$ largest eigenvalues (ordered in modulus: $|\...
- 20.2k
5
votes
Checking positive semi-definiteness of integer matrix
You can tridiagonalize an integer matrix into an integer tridiagonal matrix using Householder reflections times integers. The resulting tridiagonal matrix will be SPD iff the original is. Sylvester’...
- 1,788
Only top scored, non community-wiki answers of a minimum length are eligible