72 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_{\...
user avatar
  • 91k
31 votes

How fast can we *really* multiply matrices?

Recently there is a PhD thesis about the practical fast matrix multiplication algorithms like Strassen: Matrix multiplication is a core building block for numerous scientific computing and, more ...
user avatar
22 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 precissions is required.) ...
user avatar
  • 43.5k
21 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 ...
user avatar
20 votes

What is the time complexity of truncated SVD?

@ user40484 , fortunately your estimate for the complexity of SVD is not optimal. Otherwise, you put unemployed specialists in image compression. The complexity is in $O(\min(mn^2,m^2n))$. Assume ...
user avatar
  • 2,920
13 votes
Accepted

Why Householder reflection is better than Givens rotation in dense linear algebra?

Implementing the QR factorization with Householder rotations is cheaper ($2n^2m$ vs $3n^2m$ for a $m\times n$ matrix), and equally accurate in practice. See Section 19.6 of Higham's Accuracy and ...
user avatar
13 votes

What is the time complexity of the matrix exponential?

The exponential of a matrix is not, in general, computable explicitly. Strictly speaking, the Complexity of Matrix Exponential does not exist. Instead, you have an approximate calculation and you are ...
user avatar
  • 47.5k
13 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 ...
user avatar
12 votes
Accepted

What is the time complexity of the matrix exponential?

Moler's paper "Nineteen dubious ways to compute the exponential of a matrix, twenty-five years later" contains the following extracts: In estimating the time required by matrix computations it is ...
user avatar
10 votes
Accepted

Linearly constrained eigenvalue problem

I think Pushpendre's answer isn't quite right, but it gets you most of the way there. Getting rid of that pesky constant term is a bit tricky relative to the homogeneous case. Let's take his ...
user avatar
  • 675
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 ...
user avatar
9 votes

Efficient rank-two updates of an eigenvalue decomposition (or more generally SVD)

Just wanted to note that if one knows that the rank two update is of the form $uv^t + vu^t$ and one knows $v$ and $u$ then it is easy to find $x,y$ such that $uv^t + vu^t = xx^t - yy^t$. $x,y = \sqrt{...
user avatar
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}(...
user avatar
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 ...
user avatar
  • 47.5k
8 votes

A system of non-linear equations that is decomposable as a product -- uniqueness of solution?

The linear-in-$g$ system is uniquely solvable whenever $f_0\ne0$. therefore the solution set is parametrized by $f$ in the form $$g=f_0^{-10}P(f;a),$$ where $P$ is linear in $a$, polynomial in $f$ ...
user avatar
  • 47.5k
7 votes
Accepted

Proving that the eigenvalues of a certain matrix product are positive

That matrix is the product of two positive definite matrices, $M=UW$, with $W=A^TVA$. Hence it is similar to the symmetric matrix $U^{1/2}WU^{1/2}$, which is congruent to $W$ and thus positive ...
user avatar
7 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 ...
user avatar
  • 3,077
7 votes

Linearly constrained eigenvalue problem

Your problem has been answered at https://scicomp.stackexchange.com/questions/14096/sparse-smallest-eigenvalue-problem-on-a-linear-subspace :) Or you can read Golub's original paper Some modified ...
user avatar
7 votes
Accepted

Finding Toeplitz matrix nearest to a given matrix

The set of $n \times n$ symmetric Toeplitz matrices is $$\left\{ x_1 \mathrm M_1 + x_2 \mathrm M_2 + \cdots + x_n \mathrm M_n \mid x_1, x_2, \dots, x_n \in \mathbb R \right\}$$ where $\mathrm M_1, \...
user avatar
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 ...
user avatar
7 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 ...
user avatar
  • 93.8k
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 ...
user avatar
7 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, ...
user avatar
6 votes

Computation time of Smith normal form in Maple

(Dense) Smith Normal Form is theoretically computable in $O(\|A\| \log \|A\| N^4\log N)$ time (Arne Storjohann, 1996). Storjohann was at Waterloo at the time, so I would not be surprised if that is ...
user avatar
  • 93.8k
6 votes
Accepted

Matrix equation with Hadamard product and its own inverse involved

Removing all unnecessary parameters, we come to the equation $\Omega^{-1}=2 W\odot \Omega + B$ where $B$ is positive definite. We need to find a solution in the cone $M_+$ of positive definite ...
user avatar
  • 52.9k
6 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 ...
user avatar
  • 47.5k
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-...
user avatar
  • 51
5 votes
Accepted

Norm of triangular truncation operator on rank deficient matrices

The ratio is of order $O(\ln r)$. This follows from the fact that the triangular truncation is bounded on the Schatten class $S^p$ (=the operators $A$ on $\ell^2$ such that $\|A\|_p:= (Tr (A^*A)^{p/2})...
user avatar
5 votes

Behaviour of eigenspaces of adjacency matrices after a single change to the graph

What I'm about to say applies to the eigenvalues (at least). Here's what comes to my mind - it sprung from memory of some results of Batson, Spielman and Srivastava, mostly the paper "Twice Ramanujan ...
user avatar
  • 967
5 votes

Is this inequality involving the Frobenius norm right?

Given $\mathrm A \in \mathbb R^{m \times n}$ and $\mathrm B \in \mathbb R^{n \times p}$, let $\mathrm B \mathrm B^{\top} = \mathrm Q \Lambda \mathrm Q^{\top}$ be an eigendecomposition of $\mathrm B \...
user avatar

Only top scored, non community-wiki answers of a minimum length are eligible