All Questions
Tagged with linear-algebra na.numerical-analysis
176 questions
4
votes
1
answer
1k
views
Matrix perturbation theory
I am having matrix $M_0$ with coresponding eigenvectors and 4 eigenvalues {0,0,a,-a}. Eigenvalue $\lambda=0$ is double degenerated. Now I am appliing small perturbation $\epsilon M_1$ and want to get ...
- 41
3
votes
1
answer
413
views
Kronecker-structured matrix kernel
Let $A,B\in\mathbb{C}^{n\times 3n}$ be two matrices, and denote the Kronecker matrix product by $\otimes$. The matrix
$$
M=
\begin{bmatrix} A \otimes I_n \\\\ I_n \otimes B\end{bmatrix}
$$
has size $...
- 20.2k
4
votes
0
answers
70
views
Recovering Shared Eigenvector Set
Suppose we are given a set of $M$ pairs $\{(\vec{x}^{(i)},\vec{y}^{(i)})\}$, with
$\vec{x}^{(i)}\in\mathbb{R}^N$,
$\vec{y}^{(i)}\in\mathbb{R}^N$,
$M\gg N$ such that
$\vec{y}^{(i)} = Q^{(i)} \vec{x}^...
- 1,667
7
votes
0
answers
209
views
Numerical linear algebra: how to compute $B^TC^{−1}B$ efficiently
Hi,
my question is similar to this one. I have to compute $B^TC^{−1}B$, where $C$ is a strictly positive definite $n\times n$ matrix and $B$ is $n\times m$.
The matrix $C$ is huge ($n$ up to a ...
- 619
14
votes
2
answers
606
views
Condition number of matrix after partial orthogonalization
I'm wondering about which bounds one can put on the condition number of
a $n\times n$ square matrix which is obtained from another $n\times n$
square matrix by orthogonalizing the first $m < n$ ...
- 141
1
vote
0
answers
126
views
Matrix Minimax problem
I have the equation $\Sigma_k(M_k{p_k})V=EV$, where the $M_k$ are n*n real Hermitian matrices, $V$ is a n*n eigenvector matrix, $E$ a dim-n energy eigenvector and the $p_k$ scalar parameters. The $M_k$...
- 4,829
8
votes
1
answer
1k
views
Norm of inverse confluent Vandermonde matrix
Let $\{x_1,\dots,x_n\}$ be pairwise distinct complex numbers and $l_1+l_2+\dots+l_n=N$. The $N\times N$ confluent Vandermonde matrix is defined as
$$V=
\begin{bmatrix}
v_{1,0}&v_{2,0}&\dots&...
- 959
2
votes
0
answers
184
views
Checking for error in conjugate gradient algorithm
What is a good way to check if the any numerical error is occured in conjugate gradient algorithm. Additionally why is it not suggested to check error by checking A-orthogonality of search direction ...
- 489
8
votes
1
answer
7k
views
Upper bound on largest eigenvalue of a real symmetric $n \times n$ matrix with all main diagonal entries positive, everywhere else nonpositive
Is there a good analytic upper bound on the largest eigenvalue of a real symmetric n*n matrix with all main diagonal entries strictly positive, all other entries <=0 with typically many of them ...
- 83
1
vote
0
answers
109
views
Is there a Krylov subspace method for solving D+epsilon*S where D is diagonal, epsilon small and S skew-symmetric
I'm working on a problem that gives a matrix system of the form D + epsilon*S, where S is a skew-symmetric matrix. I'm interested in finding if any work has been done to develop a conjugate gradient ...
- 11
12
votes
5
answers
9k
views
Solving Lyapunov-like equation
The following matrix equation might be a Lyapunov-like equation, but it seems hard for me to develop a simpler way to solve it. From the computation effort, I need some help for solving the special ...
- 121
0
votes
1
answer
193
views
Ease of calculation of norm
I have SPD matrix A and two vectors z and b.
Is there exist a norm where I can calculate $||A^{1/2}b-z||$ without having to calculate $A^{1/2}b$ explicitly ?
- 489
5
votes
0
answers
160
views
reference for perturbation of projection result
Let $A$ and $B$ have the same rank and dimensions. If $P_A$ denotes the projection onto the range space of $A$, then
$$
\|P_A - P_B\|_2 \leq \|A - B\| \cdot \min (\|A^\dagger\|_2, \|B^\dagger\|_2).
$$
...
- 922
0
votes
1
answer
353
views
Moore-Penrose bound question
Suppose that we are given an equation $Ax=b$. The minimum least-squares solution is of course $x_{m}=A^{\dagger}b$. What I want to know is whether there are known bounds on $||x-x_{m}||$. In the ...
- 6,962
2
votes
2
answers
902
views
A sum of eigenvalues
Let $X$ be an $n\times n$ symmetric matrix. Suppose $\lambda_1(X)\geq \lambda_2(X) \geq \cdots \geq \lambda_n(X)$ are eigenvalues of $X$. Let $r$ be any integer with $1\leq r\leq n$. It is well-known ...
- 227
1
vote
1
answer
896
views
sign-flipping inverse
Consider this matrix:
$Z=\begin{bmatrix}23.9 & -7 & -17 \\\\ -7 & 23.9 & -17 \\\\ -17 & -17 & 33.9 \end{bmatrix}$
Its inverse is entrywise negative (you can check...) and ...
- 6,962
2
votes
1
answer
815
views
A question for solutions of perturbed linear systems
Consider a linear system
$$Ax=b\qquad (*)$$
and a sequence of perturbed linear systems $$(A+\delta A_n)x=b+\delta b_n. \qquad (n)$$
Suppose that all the linear systems are consistent (i.e., ...
- 227
3
votes
0
answers
130
views
Computing the norm of the columns of an implicitly defined matrix
I have an $n \times n$ matrix $M = \Sigma W$ where $\Sigma$ is diagonal and $W$ orthogonal. $W$ is implicitly defined, i.e. I can only perform matrix-vector products (but I also have access to $W^T$).
...
1
vote
3
answers
202
views
Solving for an operator by minimization
Please note that I am looking for numerical algorithms that will tell me what the operator is that minimizes a problem.
I have a 2x2 complex hermitian operator that is a function of two variables, so ...
- 1,313
5
votes
2
answers
4k
views
sparsity of QR decomposition
Hi, everyone!
I have a sparse $n \times n$ matrix $A$ with $nnz(A)$ denoting the number of non-zero entries in $A$. Now I use QR factorization to decompose $A$ into an orthogonal matrix $Q$ and ...
- 51
2
votes
1
answer
196
views
Relations between a set of inner products of vectors
Suppose we have n normalized vectors on an arbitrarily large Hilbert space $|A_1\rangle,\dots,|A_n\rangle$, $\langle A_i|A_i\rangle=1$ for every i. And there're $\frac{n(n-1)}{2}$ inner products $\...
- 23
6
votes
1
answer
737
views
Rank of the absolute-value matrix $|M|$ vs. rank of $M$
Let $M$ be a real matrix of rank $r$ (and let us set $M=UV^T$, with $U,V^T\in\mathbb{R}^{n\times r}$, to fix the notation).
Let $|M|$ be the matrix obtained by taking the absolute value of each entry ...
- 20.2k
7
votes
2
answers
3k
views
Factorizing a block symmetric matrix
Let $X,Y\in\mathbb{R}^{n\times n}$ be symmetric matrices. You may assume that $X$ is positive semidefinite and $Y$ negative semidefinite, if needed, but not that they are invertible.
I would like to ...
- 20.2k
8
votes
2
answers
583
views
Efficiently computing a few localized eigenvectors
Let $H = \triangle + V(x) : \mathbb{R}^2 \rightarrow \mathbb{R}^2$. I am interested in domain decomposition for an eigenproblem involving $H$.
The lowest 1000 eigenfunctions of $H$, $ \psi_i $, can ...
- 817
0
votes
3
answers
7k
views
Find an $N$-dimensional vector orthogonal to a given vector
I'm writing an eigensolver and I'm trying to generate a guess for the next iteration in the solve that is orthogonal to to all known eigenvectors calculated thus far. This means that if I have only ...
1
vote
0
answers
298
views
Norm preserving matrix fix
Hello,
I'll state the problem first and than I'll a little bit of motivation.
Lets be given regular matrix $M \in \mathbb{R}^{n\times n}$ and norm $||.||$ in $\mathbb{R}^{n}$. Define $$ U =\{ L\in \...
2
votes
1
answer
1k
views
On an eigenvalue inequality
Let $\lambda_1 (\cdot)$ be the larger absolute value
eigenvalue of a $2\times2$ matrix and $\lambda_2 (\cdot)$
the smaller absolute value eigenvalue of a $2\times2$ matrix, i.e.
$|\lambda_1 (\cdot)| \...
- 29
3
votes
4
answers
4k
views
Fast multiplication of constant symmetric positive-definite matrix and vector.
Consider the matrix $H=H^T$, $H>0$, $H \in R^{n \times n}$, and the vector $v \in R^n$. In a numerical algorithm, I need to compute the product $b = Hv$. Right now I am following the naive approach:...
- 33
0
votes
1
answer
307
views
Comparing iterative methods for linear systems
For a tridiagonal matrix of the from
\begin{bmatrix}
a & -b & \newline
-b & a & -b \newline
& \ddots & \ddots & \ddots \newline
& & & & -...
2
votes
2
answers
599
views
Eigenvectors of a diagonalizable matrix
Suppose we have a n-by-n symmetric matrix K which can be factorized in a way, K = H * L * H', where L is a m-by-m diagonal matrix and H is a n-by-m matrix. In addition, let's assume n <= m.
Can we ...
- 21
7
votes
3
answers
3k
views
Algorithm for the smallest (algebraic) eigenvalues of a symmetric (sparse) matrix
Hi,
I'm looking for a way to get the negative eigenspace of a large (sparse) symmetric matrix. This matrix is basically a discretized version of the operator $-\Delta + V$, $V$ negative, on some ...
- 411
10
votes
1
answer
4k
views
Special considerations when using the Woodbury matrix identity numerically
Are there any special considerations when using the Woodbury matrix identity numerically? What is the best metric for numerical stability in this case? Can anyone point me to a good reference?
The ...
- 211
2
votes
1
answer
2k
views
How to do (m)Gram-Schmidt orthogonalization with integers ? (real life problem) ("mathematicalized reformulation")
New edition of the question, "mathematicalized" (thanks to Gerhard).
Consider and integer valued n*n matrix M, with integers elements in the range -N < m < N.
I want to find integer-valued ...
- 24.9k
13
votes
2
answers
1k
views
Seeking proof for linear algebra constraint problem.
Given a symmetric real matrix with a zero diagonal $M$, I am trying to find a diagonal matrix $D$, such that the matrix $M + D$ is positive definite, and $(M+D)^{-1}$ has a diagonal consisting of all ...
- 379
7
votes
1
answer
505
views
Numerical linear algebra: how to compute $b^TA^{-1}b$ efficiently
What is the most efficient way to compute $b^TA^{-1}b$ for a given $A$ and $b$?
Do we have to calculate $A^{-1}b$, or is this not necessary?
edit: I forgot to mention that A is symmetric and ...
- 493
4
votes
0
answers
382
views
Pseudoinverse of column submatrix, from pseudoinverse of entire matrix.
Hello,
I am working on a numerical method for the least-squares solution of a linear system. I know that I can approximate the solution to $Ax=b$ with $x=A^+b$, where $A^+$ is the Moore-Penrose ...
- 41
8
votes
2
answers
2k
views
Algorithm for solving systems of linear Diophantine inequalities
So, I posted on StackOverflow looking for a reasonably fast algorithm to solve systems of linear Diophantine inequalities and was pointed to this article by Cheng-Zhi Gao and Yu-Lin Dong. The problem ...
- 3,079
22
votes
9
answers
17k
views
Fast evaluation of polynomials
Hello everybody !
I was reading a book on geometry which taught me that one could compute the volume of a simplex through the determinant of a matrix, and I thought (I'm becoming a worse computer ...
- 1,654
2
votes
2
answers
402
views
Maximization of a matrix product by iterative methods
This might not be very difficult, but I think I may have gotten a little confused.
Suppose we are given a matrix A, and would like to find the vector x of modulus 1 which maximises the product xt A x ...
- 949
5
votes
4
answers
2k
views
Determining a recurrence relation
I would like to solve the general problem of determining a linear recurrence relation that fits a given integer sequence of length $n$, or stating that none exists (with fewer than $n/2-k$ ...
- 9,114
2
votes
0
answers
187
views
Recovering a linear map from a non-linear approximation
The problem described here is algorithmic. We are given "black box access" to a map $f:R^d\to R^d$. By this we mean that one may query the value of $f(v)$ for an arbitrary $v\in R^d$.
We assume that ...
10
votes
5
answers
8k
views
Shifted QR algorithm—why does the shift help?
I read that a way to speed up the convergence rate of the QR algorithm is to shift the target
matrix. It is not so clear to me why this helps. The convergence rate depends on the
minimum gap between ...
- 353
1
vote
2
answers
262
views
How to approx. decompose a sym. p.d. matrix M into X'X?
M: pxp symmetric p.d. matrix with unit diagonals
n: number much smaller than p
Want a nonrandom nxp matrix X such that X'X is
close to M element-wise. If n gets larger, hopefully
difference ...
- 21
4
votes
1
answer
1k
views
An optimization problem in numerical linear algebra
Provided two diagonal real matrix which has positive entries, $V$ and $U$.
Find a real matrix $A$, satisfying $A^TA=a^2I$ for some scalar $a$, to minimise
$\left|A^TVA-U\right|\quad\quad(*)$ ...
- 135
10
votes
4
answers
2k
views
How to solve Ax=b incrementally ?
Hi, everyone.
What I am struggling is the following problem. I have a linear matrix equation $Ax=b$, where $A$ is a known $n \times n$ large sparse real matrix, $x$ and $b$ are known $n \times 1$ ...
- 101
3
votes
1
answer
346
views
enlarge the separation between two matrices
The separation between two square matrices $A$ and $B$, often used as a measure of the sensitivity of invariant subspace problems, is defined as
$$
\operatorname{sep}(A,B)=\min_{X\neq 0}\frac{\left\...
- 20.2k
11
votes
1
answer
3k
views
Best way to find a closest vector in a lattice
Let $v_1,\dotsc,v_n$ be linearly independent vectors in $\mathbb{R}^n$, and let $\Lambda=\bigoplus_{i=1}^n \mathbb{Z}v_i$. The question is, given a vector $w$ in $\mathbb R^n$, find the element $v$ ...
- 351
2
votes
3
answers
285
views
is there any efficient way to compute the follow matrix equations easily
Let $A$ and $D$ are $n\times n$ diagnal matrices, and $B$ is an $n\times n$ orthogonal matrix. Is there any efficient way to compute the follow matrix equations easily?
$\sum_{i=0}^{k} A^i \cdot B^T \...
- 21
3
votes
0
answers
681
views
How to bound the second largest eigenvalue of a transition matrix of a non-irreducible Markov chain?
I have found several bounds (e.g., Cheeger, Poincare) for the case that the Markov chain is irreducible and reversible, however my Markov chain has one absorbing state. Any bound would be helpful, but ...
- 31
0
votes
1
answer
2k
views
Solving 5 eqns with 6 unknowns in a 2x3 contingency matrix, is there a unique solution? [closed]
Background
I have the following equations:
$$a+b+c=6$$
$$d+e+f=15$$
$$a+d=5$$
$$b+e=7$$
$$c+f=9$$
This is a 2x3 matrix $[a b c, d e f]$ where the marginal totals are fixed. In addition, all of the ...
- 225