All Questions
Tagged with linear-algebra na.numerical-analysis
176 questions
2
votes
1
answer
3k
views
Is it possible to decompose a symmetric, positive definite matrix in this way?
Let $\Sigma$ be a symmetric positive definite matrix. Then the Cholesky decomposition gives us $\Sigma=LL'$ where $L$ is lower triangular and unique.
Under what conditions (if any) does there exist ...
- 269
9
votes
1
answer
385
views
Adding a multiple of the Identity to a LU factorized matrix
Suppose a square, dense, symmetric matrix $A$ has been factorized into $L$ and $U$ components by performing a LU decomposition. Now let $B = A+\lambda I$. Is there any way to efficiently compute the ...
- 339
1
vote
2
answers
6k
views
Square root of non-positive definite matrix
Finding square root of matrices using Cholesky decomposition is limited to positive definite matrices. Any other method to find square root of matrix which has some diagonal values approximately zero (...
- 11
6
votes
4
answers
7k
views
Why do we want to have orthogonal bases in decompositions?
In the decompositions I encountered so far, we all had orthogonal set of bases. For example in Singular Value Decomposition, we had orthogonal singular right and left vectors, in [discrete] cosine ...
- 497
4
votes
3
answers
3k
views
Making MATLAB svd robust to transpose operation
I'm playing with MATLAB's svd function to compute the svd of
[ 1 4 7 10
2 5 8 11
3 6 9 12 ]
When I type [U1, ~, ~] = svd(...
- 497
6
votes
2
answers
2k
views
Computation of a Drazin inverse
I need to compute the Drazin inverse $A^D$ of a singular M-matrix $A$, i.e., a matrix in the form $A=\lambda I -P$, where $P$ has nonnegative entries and $\lambda$ is the spectral radius (Perron value)...
- 20.2k
4
votes
0
answers
453
views
Convergence of the relaxation method for every parameter in the relevant disk
For large size matrices, the resolution of linear systems $Ax=b$ is often done iteratively. The matrix $A$ is split as $A=M-N$, with $M$ invertible, and one performs
$$x^{k+1}=M^{-1}(Nx^k+b).$$
The ...
- 52.3k
1
vote
1
answer
383
views
Relaxation Scheme for $Au=f$ error analysis
Hello
I'm trying to answer this question, but am completely stuck.
Argue that in analyzing the error in a stationery linear relaxation scheme applied to $Au=f$, it is sufficient to consider $Au=0$ ...
- 579
5
votes
5
answers
1k
views
solving series of linear systems with diagonal perturbations
I would like to solve a series of linear systems Ax=b as quickly as quickly as possible. However, the systems are related. Specifically, each matrix A is given by:
cI + E
where E is a fixed sparse, ...
- 135
2
votes
0
answers
241
views
subspace separation and M-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
109
votes
19
answers
38k
views
Why were matrix determinants once such a big deal?
I have been told that the study of matrix determinants once comprised the bulk of linear algebra. Today, few textbooks spend more than a few pages to define it and use it to compute a matrix inverse. ...
6
votes
3
answers
2k
views
Conjugate Gradient for a "slightly" singular system.
Suppose I have a symmetric $N \times N$ matrix A which has a one-dimensional Nullspace $N$. A is positive definite on $N^\bot$. In my case $N$ is the space of constant vectors (i.e. generated by ...
- 617
8
votes
5
answers
15k
views
Eigenvalues of A+B where A is symmetric positive definite and B is diagonal
If I have a symmetric positive definite matrix A and a diagonal matrix B, and I know the eigenvalues of both A and B (by iterative numerical computation in A's case and trivially for B), is there any ...
- 135
3
votes
2
answers
3k
views
distributed incremental SVD
Hello all,
I need some theoretical pointers (formulas, articles, online links) on how to merge Singular Value Decompositions (SVD) of two matrices (two different sets of observations over the same ...
- 93
12
votes
2
answers
8k
views
Is there a way to simplify block Cholesky decomposition if you already have decomposed the submatrices along the leading diagonal?
Let's say we have a block matrix $ M =\left( \begin{array}{ccc}
A & B\\
B^{*} & C \end{array} \right)$ where $M$ is positive definite. ($A$ and $C$ are also positive definite.)
There is a ...
3
votes
0
answers
2k
views
Eigenvalue Problems with Linear Constraints
The motivation for this problem comes from trying to develop a simple way to decompose domains into non-overlapping subdomains to solve for the eigenvalues of some differential operator. The idea is ...
- 543
4
votes
1
answer
548
views
O(n^2) algorithm to approximate the sum of the log of the singular values of a matrix
Given an $M \times N$ matrix of rank $N$ ($M \ge N$) with $i^{th}$ singular value $\sigma_i$, does their exist an $O(M^2)$ algorithm for approximating the sum $ H =\sum_{i=1}^N \log(\sigma_i)$ with ...
- 188
15
votes
9
answers
9k
views
Exponential of large matrices
I want to make a diffusion kernel, which involves $e^{\beta A}$, where A is a large matrix (25k by 25k). It is an adjacency matrix, so it's symmetric and very sparse.
Does anyone have a ...
- 151
21
votes
9
answers
19k
views
What is the best algorithm to find the smallest nonzero Eigenvalue of a symmetric matrix?
see title.
An algorithm is 'good' if it is able to distinguish between zero Eigenvalues and nonzero Eigenvalues.
- 979
1
vote
0
answers
1k
views
Covariance matrix formula interpretation - what am I missing?
I'm reading a paper that outlines the calculation of a covariance matrix like the following:
$C=\displaystyle\sum^{N_b}_{i=1}\vec{x}_i\vec{x}_i^T$
What is the order of this matrix? My interpretation ...
- 111
1
vote
2
answers
540
views
Using Wavelet Transforms to Approximate Matrices
It's a long time since I worked on this kind of problem, so please bear with me.
I have an approximate inverse matrix that I'm using as a preconditioner to solve the conjugate gradient method. ...
- 221
0
votes
2
answers
4k
views
Convergence of iterative algorithm.
For quite a long time I'm trying to prove convergence of an iterative algorithm in case of a particular system of nonlinear equations.
Here are some characteristics of this system:
It consists of n ...
1
vote
0
answers
393
views
iterated characteristic polynomials
If I have $N$ $M\times M$ symmetric positive definite matrices $A_i$ and an $N\times N$ positive semi-definite symmetric matrix B, let the $N\times N$ matrix $C_{ij}(\lambda)=B_{ij}$ for $i\ne j$ and $...
- 11
2
votes
1
answer
728
views
Cubic spline of a two-variable function
So, I am aware of how to (both iteratively and using a linear equation) compute the cubic spline of a one-variable function with $m$ control points. However, I am not sure how to do any type of spline ...
- 21
5
votes
1
answer
2k
views
Inverting a covariance matrix numerically stable
Given an $n\times n$ covariance matrix $C$ where $n$ around $250$, I need to calculate $x\cdot C^{-1}\cdot x^t$ for many vectors $x \in \mathbb{R}^n$ (the problem comes from approximating noise by an $...
- 51
7
votes
4
answers
2k
views
Is there a name for the matrix equation A X B + B X A + C X C = D?
I happen to be working on a problem that reduces to solving the following equation:
$$\mathbf{A X B} + \mathbf{B X A} + \mathbf{C X C} = \mathbf{D}$$
where A through D are known matrices ( A, B, D ...
- 1,890