Skip to main content

All Questions

Filter by
Sorted by
Tagged with
1 vote
0 answers
111 views

Solving a block tridiagonal system with diagonal perturbations

Say we have a block tridiagonal matrix, $T \in \mathbb{R}^{NL \times NL}$, with constant off diagonals, $\mathbf{B} \in \mathbb{R}^{L\times L}$, given by $$ T = \begin{bmatrix} \mathbf{A}_1 & \...
21 votes
3 answers
51k views

What is the time complexity of truncated SVD?

Full SVD, on an $m \times n$ matrix $A$, [U,S,V] = svd(A), would cost $O(m^2n + mn^2 + n^3)$ time. But what is the time complexity if we only need the $k$ largest ...
1 vote
1 answer
326 views

For the purposes of solving linear equations, is there a fast decomposition that works for all Hermitian matrices?

Let $A$ be an arbitrary Hermitian matrix. Is there a way of efficiently factorizing $A$ for the purposes of solving $Ax = b$ for arbitrary $b$? There are two decompositions I'm aware of that nearly ...
5 votes
1 answer
401 views

Best orthogonal approximation of rank 1 matrix

Let $X=\lambda_0u_0v_0^T\in\mathbb{R}^{n\times n}$ be a rank 1 matrix where $\lambda_0\in\mathbb{R}$, $u_0,v_0$ are of unit Euclidean norm. What is the solution of the following problem? $$\hat{X}=\...
11 votes
1 answer
896 views

Decide if a matrix is transposable

A matrix $M$ is called transposable if it can be transformed into its transpose $M^t$ via row and column permutations. Is there an efficient a way/algorithm to decide if a given matrix is ...
8 votes
1 answer
1k views

Square root of a large sparse symmetric positive definite matrix

I am trying to calculate $$Y = A^{\frac 12} X$$ where $A$ is a very large and sparse positive definite matrix, say, $10^4 \times 10^4$. Matrix $X$ is known and, say, $10^4 \times 100$. Is there any ...
0 votes
1 answer
572 views

Recurrence Equation and Matrix Convergence

To begin with, let us give the conceptual background needed to expose the problem. First of all, we shall consider the set $\mathbb{L}^{n} = \mathbb{R}^{n}_{\geq0} = \{\overrightarrow{x}\in\mathbb{R}^{...