All Questions
7 questions
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}^{...