# Tagged Questions

**1**

vote

**0**answers

37 views

### Lanczos algorithm with thick restart on a dynamic matrix

currently, I'm working on a way to compute the 2 biggest eigenvalues of a real, symmetric, huge and sparse matrix that changes a few entries from time to time. The problem should be solved using an ...

**3**

votes

**0**answers

68 views

### What do we know about the generalized eigenvalue problem involving a projector?

Consider a matrix $A\in\mathbb{R}^{n\times n}$ and a projector $P\in\mathbb{R}^{n\times n}$.
Are there results regarding the generalized eigenpairs $(v,\lambda)$ of the generalized eigenproblem
...

**0**

votes

**0**answers

45 views

### Generalized Eigenvalue problem solution

$\circ$ Consider the following eigenvalue problem : $$XY^{T}YX^{T}w=\lambda XX^{T}w \hspace{0.5cm} (1)$$
Matrices $XY^{T}$ and $XX^{T}$ $\in \mathbb{R}_{n \times n}$ are positive semi-definite and ...

**1**

vote

**0**answers

94 views

### Algorithms to compute largest gap between smallest nonzero eigenvalues of sparse symmetric matrix

I am looking mainly for implementations but also for theoretical algorithms to compute gaps between smallest positive eigenvalues of symmetric, singular matrix or real numbers.
To be precise, I want ...

**1**

vote

**1**answer

53 views

### Augmenting orthonormal system into complete orthonormal system in a numerically stable way

Let us suppose we have a, say, 10 dimensional real space with 3 orthogonal unit vectors given. How do I complete this orthonormal system with 7 additional vectors into a complete ONS in a way that is ...

**1**

vote

**0**answers

40 views

### Nontrivial Matrix-estimate

I try to proof the following estimate:
\begin{align}
h' W^{-1} H W^{-1} h \geq c h' H h \qquad c>0, \qquad\qquad (1)
\end{align}
where $h\in\mathbb{R}^{K-1}$ and ...

**1**

vote

**1**answer

121 views

### Eigenvalue problem with quadratic constraints

$\circ$ Consider the following eigenvalue problem : $$Ax=\lambda x \hspace{0.5cm} (1)$$
where matrice $A \in \mathbb{R}_{n \times n}$ is a positive semi-definite with eigenvectors $x = ...

**2**

votes

**1**answer

78 views

### Updating $LU$ decomposition after adding a sparse matrix

How many elements of $LU$ decomposition of a symmetric matrix change after adding a sparse symmetric matrix? Is it more efficient to recompute $LU$ decomposition after adding a sparse matrix comparing ...

**11**

votes

**2**answers

398 views

### How to project a vector onto a very large, non-orthogonal subspace

I have a difficult problem.
I have a very large, non-orthogonal matrix $A$ and need to project the vector $y$ onto the subspace spanning the columns of $A$. If this were a small matrix, I would use ...

**4**

votes

**0**answers

94 views

### Preconditioner for finding the smallest eigenpairs of a large, but structured, matrix

I'm trying to find the eigenvector corresponding to the second smallest eigenvalue of a large $(4,000,000 \times 4,000,000)$ matrix $L$. $L$ is a graph Laplacian, with the following structure: $L = D ...

**2**

votes

**1**answer

154 views

### Possible pathological properties of positive definite matrix

Suppose $A$ is a positive definite matrix such that
$$I \preceq A \preceq 1.01I.$$
Is it possible that
$$\sum_{i=1}^n A_{1i}$$
can be arbitrarily large?
Thanks,
Jack

**7**

votes

**0**answers

115 views

### Problems where Conjugate gradient works much better than GMRES

I am interested in cases where Conjugate gradient works much better than GMRES method.
In general, CG is preferable choice in many cases of SPD because it requires less storage and theoretical bound ...

**9**

votes

**2**answers

346 views

### Computing a large permanent

Is there a practical way to compute the permanent of a large ($91 \times 91$) $(0,1)$ matrix?
I have tried to use the matlab function written by Luke Winslow which works great for smaller matrices ...

**7**

votes

**1**answer

130 views

### Who first observed that Conjugate Gradient for Symmetric Positive Definite linear systems is a Krylov method?

Conjugate gradient was originally presented in the 50's before the modern understanding of Krylov subspaces (and the resulting iterative methods) was fully realized. As such, the method was derived ...

**4**

votes

**1**answer

588 views

### Efficient computation of Markov chain transition probability matrix

Consider a continuous Markov chain $X = (X_t)$ on a finite state space and let $Q$ be the (given) transition rate matrix. This matrix is very sparse, with non-zero values on 3 diagonals only (so from ...

**1**

vote

**1**answer

148 views

### integral basis of orthogonal complement

Suppose there are $r$ linearly independent vectors $v_1,\dots,v_r\in \mathbb{R}^n$, all of them have integer-valued entries and $\|v_i\|_\infty\leq m$ for some integer $m$.
My goal is to find an ...

**0**

votes

**1**answer

76 views

### Avoiding epsilon in mixed integer linear and quadratically constrained programs

I would like to represent the following constraint as MILP constraint where $x \in [a, b]$ with fixed $a, b \in \mathbb{R}$ and $y \in \lbrace 0, 1 \rbrace$.
$(x = 0 \wedge y = 1) \vee (x \neq 0 ...

**4**

votes

**1**answer

210 views

### best rank r approximation for non-Frobenius norm

The best rank $r$ approximation to a given matrix $M$ in Frobenius norm, according to Eckart-Young theorem, is truncated SVD - just keep $r$ largest singular values. What if I need to construct best ...

**4**

votes

**1**answer

491 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 ...

**3**

votes

**1**answer

89 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 ...

**4**

votes

**0**answers

45 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)} ...

**5**

votes

**0**answers

131 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 ...

**13**

votes

**2**answers

287 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$ ...

**1**

vote

**0**answers

96 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 ...

**4**

votes

**1**answer

299 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}
...

**2**

votes

**0**answers

132 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 ...

**4**

votes

**1**answer

1k views

### Upper bound on largest eigenvalue of a real symmetric n*n matrix with all main diagonal >0, everywhere else <=0

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 ...

**1**

vote

**0**answers

56 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 ...

**5**

votes

**3**answers

443 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 ...

**0**

votes

**1**answer

159 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 ?

**5**

votes

**0**answers

124 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).
$$
...

**0**

votes

**1**answer

214 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 ...

**2**

votes

**2**answers

361 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 ...

**1**

vote

**1**answer

292 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 ...

**2**

votes

**1**answer

222 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., ...

**2**

votes

**0**answers

106 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

163 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 ...

**2**

votes

**2**answers

501 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 ...

**2**

votes

**1**answer

122 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 ...

**5**

votes

**1**answer

418 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 ...

**5**

votes

**2**answers

618 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 ...

**7**

votes

**2**answers

456 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 ...

**1**

vote

**0**answers

181 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 ...

**1**

vote

**1**answer

694 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)| ...

**2**

votes

**4**answers

677 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 ...

**0**

votes

**0**answers

186 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

544 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 ...

**7**

votes

**2**answers

830 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 ...

**5**

votes

**1**answer

471 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 ...

**2**

votes

**1**answer

1k 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 ...