Questions tagged [cholesky-decomposition]
The Cholesky decomposition is a decomposition of a Hermitian, positive-definite matrix into the product of a lower triangular matrix and its conjugate transpose.
115
questions
0
votes
0
answers
40
views
The Numerical Issues of Computing The QR-Decomposition Using CholeskyQR
I have an application where I need to compute the QR-decomposition (in fact I only need $R$) of a matrix $A\in \mathbb{R}^{m \times n}$ ($m > n$). The matrix has a fixed number of columns, but the ...
- 1
4
votes
1
answer
125
views
Let $X,Y,Z$ be three random variables such that the correlation coefficients $\rho_{XY}=0.2, \rho_{YZ}=0.2$, what values can $\rho_{XZ}$ take?
Let $(X,Y,Z)^T$ be jointly normal variable with zero mean such that the correlation coefficients $\rho_{XY}=0.2, \rho_{YZ}=0.2$, what values can $\rho_{XZ}$ take?
Prove that there exists a ...
- 1,437
1
vote
1
answer
39
views
Best way to compute $A^{-1}$ when the Cholesky decomposition $A=LL^T$ is known
Suppose $\mathbf{A}$ is symmetric positive definite, and that I have available the Cholesky decomposition of $\mathbf{A}=\mathbf{L}_A\mathbf{L}_A^T$. I want to know $\mathbf{A}^{-1}$. Which of the two ...
- 11
1
vote
0
answers
26
views
Solution to Triangular Systems with Cholesky Factor
The answer in this post describes the solution to this linear system
$$
\begin{aligned}
Ax &= b \\
L L^{T} x &= b
\end{aligned}
$$
as solving the two triangular systems.
$$
\left \{
\begin{...
- 163
0
votes
1
answer
32
views
Cholesky decomposition for symmetric positive semi-definite matrices
On page 5 here: https://stanford.edu/class/ee363/lectures/lmi-s-proc.pdf
$A$ and $B$ are decomposed into $A^{1/2} A^{1/2}$ and same for $B$.
Is this from Cholesky decomposition? Can someone prove ...
- 539
0
votes
0
answers
24
views
Deriving a Cholesky decomposition algorithm
I am studying numerical linear algebra using Lloyd Trefethen's book. In the chapter on systems of linear equations, I am reading about the Cholesky decomposition. I understand existence and uniqueness,...
- 3,823
0
votes
1
answer
16
views
What does $\mbox{cholesky}(P)^{-1} [\cos(\theta), \sin(\theta)]$ correspond to?
I'm trying to understand a function, and its name isn't really helping me (I've found resources similar to this and this but this is either R or not exactly "ELLIPLOT" and I'm not sure I ...
0
votes
0
answers
61
views
Cholesky decomposition for a Hermitian matrix in SDP
I have a variable matrix $W$ that is Hermitian and is used in two SDP problems.
Problem 1 has constraints that depend on the real diagonal elements of $W$.
Example of the constraint is $W_{ii}+x_{ij}...
0
votes
1
answer
65
views
Gradient through Cholesky decomposition
For a positive definite matrix $\Sigma$, its Cholesky decomposition is defined as follows:
$$\Sigma = R^T R$$
where $R$ is an upper-triangular matrix where non-zero elements $\in \mathbb{R}$. I want ...
- 240
0
votes
0
answers
17
views
Legacy code solving least squares adjustments
I was given the task to maintain an old library that, among other things, claims to calculate least squares adjustments. I have read and understood some theory behind it, however I still have troubles ...
- 11
0
votes
0
answers
92
views
Cholesky decomposition of large matrices
I am trying to obtain the Cholesky decomposition of a huge $150,000 \times 150,000$ sparse matrix with randomly distributed non-zero elements. I have only the entries for which the values are non-zero....
- 31
2
votes
1
answer
72
views
Square Root of Symmetric Block Matrix
Let $ X\in\mathbb{R}^{(N+1)n}, U\in\mathbb{R}^{Nm}$ be two random variables, with $N,n,m >0$ positive integers.
The covariances of $X$ and $U$ are $\Sigma_{X} = (I + BK)\mathcal{S}(I + BK)^\...
- 203
-1
votes
2
answers
153
views
How does Cholupdate work?
I have made some MATLAB code for Cholupdate algorithm. The problem is that some times it works, some times not.
...
- 2,497
1
vote
1
answer
104
views
Show that the lower triangular matrix $L=(l_{ij})i,j=1,…,n∈Rn×n$ resulting from Cholesky decomposition has the same band width m as the band matrix A
Let $ A=\left(a_{i j}\right)_{i, j=1, \ldots, n} \in \mathbb{R}^{n \times n} $ be a symmetric and positive definite band matrix with band width $ m \in \mathbb{N} $, i.e. $ a_{i j}=0 $ for $ i, j \in \...
- 125
0
votes
1
answer
28
views
Triangular solver memory complexity
Does anybody know about the memory complexity of triangular solver?
PyTorch Documentation: https://pytorch.org/docs/stable/generated/torch.triangular_solve.html
More about Triangular solver: http://...
- 55
0
votes
0
answers
21
views
Cholesky factorization of the precision matrix [duplicate]
Assume that I have a (symmetric, positive semi-definite) covariance matrix $\mathbf{\Sigma}$, and the following identity
$$\mathbf{\Sigma}=\mathbf{L}^{-1}\mathbf{L}^{-\intercal} \tag{1}$$
where $\...
- 855
0
votes
0
answers
67
views
Cholesky decomposition rank one update using sum of columns
Suppose I have a matrix $M$ that is symmetric positive definite of size n, then I decompose it using Cholesky decomposition and get $L$:
$$
M = LL^T
$$
Let $L_i$ be the i-th column of L:
$$
L = [L_1, ...
- 195
1
vote
0
answers
28
views
Invariance of columns in update of Cholesky decomposition
Suppose I have a matrix $M$ that is symmetric positive definite of size n, then I decompose it using Cholesky decomposition and get $L$:
$$
M = LL^T
$$
Let $L_i$ be the i-th column of L:
$$
L = [L_1, ...
- 195
-1
votes
1
answer
45
views
Can we deduce this property for 2 norm with respect to sub matrix of Cholesky factorization? [closed]
We have $A \in \mathbb{R}^{n \times n}$ which is symmetric and positive-definite. Also, $A$ is a block matrix:
$$A = \begin{pmatrix} A_{11} & A_{21}^{\top} \\ A_{21} & A_{22} \\ \end{pmatrix}.$...
- 507
4
votes
1
answer
75
views
Positive semi-definitness of modified RBF Kernel
Let's say I have an imaging space made of 100x100 pixels and I want to make a covariance matrix using RBF kernel (Gaussian kernel). In other words, say the covariance matrix is $C\in\mathbf R^{10000\...
- 43
1
vote
0
answers
44
views
Rank-2 update for Cholesky factor
What is the most efficient way to update Cholesky factor if we have rank 2 update to the initial matrix?
In other words:
Given a positive-definite matrix A where $$ A = L^T L , A \in \mathbb{R}^{n \...
2
votes
0
answers
353
views
Efficient algorithm of rank-one update of the Cholesky decomposition
Suppose that I have a symmetric positive definite matrix $X$ and that I Cholesky-decompose it
$$ X = L L^T $$
Now, given a vector $v$, suppose we want to decompose the following matrix using the ...
- 195
0
votes
0
answers
47
views
Solving $XX^T=A$ for complex $A$
Let $A$ be a complex $n\times n$ matrix. When does $XX^T = A$ have a solution?
My attempt:
Since $(XX^T)^T=XX^T$, $A$ has to be a symmetric matrix to have a solution.
After googling, I got to know ...
- 1,057
0
votes
0
answers
39
views
Cholesky factorization of A'QA
My goal is to compute the Cholesky factorization $A'QA$ efficiently, where $Q$ is a large, sparse positive definite matrix and $A$ is typically dense and has significantly fewer columns than $Q$.
If $...
- 109
1
vote
1
answer
55
views
What are the benefits of having fewer non-zero entries in the Cholesky decomposition of a matrix?
The question begins when I read the following paper.
Carlotta Giannelli, Bert Jüttler, Hendrik Speleers, THB-splines: the truncated basis for hierarchical splines, Computer Aided Geometric Design, ...
- 117
1
vote
0
answers
35
views
If $LL^T = (DC)(DC)^T$, where $L,D,C$ are matrices, does $L = DC$?
The variance-covariance matrix $\Sigma$ is related to the correlation matrix $\varrho$ by the equation
$\Sigma = D \varrho D$, where $D = \sqrt{\text{diag}(\Sigma)}$
Now consider the Cholesky ...
- 877
0
votes
1
answer
43
views
Do you have to start with the first row during LU decomposition?
I guess I've never run into this pretty simple problem, but I'm doing a Cholesky Factorization of the matrix shown below, and ran into some weird ambiguity in how I usually do $LU$ decomp:
$$ A = \...
1
vote
1
answer
133
views
What is the Cholesky decomposition of an upper triangular matrix?
A similar question is asked here, but for LU decomposition instead of Cholesky, which makes this less trivial. I am using an algorithm (in Matlab) that spends a lot of time computing the Cholesky ...
- 25
0
votes
1
answer
104
views
Cholesky decomposition of a block-matrix with constant spherical diagonal and off-diagonal blocks
Consider $M$ an $nN\times nN$ block matrix which can be written as $n\times n$ blocks, with all the "diagonal" blocks equal $A = a I$ and all the "off-diagonal" blocks equal $B = b ...
- 43
0
votes
0
answers
34
views
Expectation of Cholesky quadratic form of random matrix
Let $X = CC'$ be a symmetric positive definite random matrix, $C$ its lower Cholesky factor and $Y$ a diagonal matrix with positive constants as diagonal elements.
Given we have the expectation
$$
\...
- 554
0
votes
2
answers
73
views
Factorization of symmetric positive matrix
I have the following question:
Let $A$ be a symmetric positive definite real matrix. Then we are asked to show that there exits two matrices, $C$ and $D$ where $C$ is lower triangular with $1$s in the ...
- 1,426
0
votes
0
answers
50
views
Homework - Gaussian Process with Cholesky Decomposition
For b), I have:
But I can't seem to fit the "facts" given in the problem anywhere.
What am I missing here?
Any help/hint is appreciated!
- 369
0
votes
0
answers
63
views
How can I find the square root of symmetric positive definite matrix $A$ by using Cholesky decomposition?
Assume that we have a symmetric positive definite matrix $A$ and we want to find the matrix square root of that matrix $A$ using Cholesky decomposition.
$$A = R^TR$$
Where $R$ is upper triangular ...
- 2,497
2
votes
1
answer
154
views
What is the purpose of Cholesky decomposition in the following two stochastic processes?
I have two stochastic processes $x$ and $y$ such that:
$$ dx(t) = -ax(t)dt + \sigma dW_1(t) \\
dy(t) = -by(t)dt + \eta dW_2(t) $$
where $W_1$ and $W_2$ are Brownian motions.
The text in my book ...
- 111
0
votes
1
answer
103
views
Can every complex positive definite matrix have a cholesky decomposition?
I am aware of the fact that every positive definite matrix $A \in \mathbb{R}^{n\times n}$ admits a Cholesky decomposition, but I am wondering if this holds for complex positive definite matrices too.
...
- 37
1
vote
0
answers
58
views
Why is the Cholesky power iteration valid?
Another user claimed he/she could show the same iteration is well-defined if $A$ is 2-by-2 SPD. How can I show that this iteration method is well-defined for a SPD $A$ of any size? More specifically, ...
- 711
1
vote
1
answer
93
views
Recover a set of vectors from a Gram matrix that have conjugate symmetry
I have a set of complex column vectors concatenated in a matrix, $X$, for which I have the corresponding Gram matrix $G = X^*X$. Because of the basis that I'm using (complex spherical harmonics), the ...
- 25
0
votes
1
answer
50
views
Is it possible to find the orthogonal matrix, $Q$, in $QMQ^\text{T} = A$?
Is there a way to solve for the orthogonal matrix, $Q$, in
$QMQ^\text{T} = L^\text{T}GL$
where $M$ is a known anti-diagonal matrix and the right hand side is known ($L$ is lower-triangular from a ...
- 25
1
vote
1
answer
45
views
Pseudo-whitening problem of matrix-based data
Whitening: When you have a set of vectorial observations, i.e. $\{\boldsymbol{v}_i\in\mathbb{R}^n:i\in[1,N]\}$ you can standardize and decorrelate each dimension $d\in[1,n]$ using Cholesky-whitening:
$...
- 133
2
votes
1
answer
163
views
Computation of Cholesky decomposition of Gram matrix from its components
Let's assume I have a tall matrix $\mathbf{X} \in \mathbb{C}^{m\times n}$, where $m \gg n$. I form the Gram matrix $\mathbf{A} = \mathbf{X}^*\mathbf{X}$, where $\mathbf{A} \in \mathbb{C}^{n\times n}$ ...
- 175
0
votes
0
answers
23
views
why use svd() to invert a Hermitian matrix?
In MATLAB, I compared elapsed time to invert a Hermitian matrix using inverse(), svd(), and ...
- 21
0
votes
0
answers
27
views
Expanding solution of linear equations with Cholesky factors to matrix.
Suppose $B$ is $N\times N$ matrix and $A$ is $N\times M$ matrix.
$A$ and $B$ is given, and Cholesky factor $L$ is also given which satisfy $B=LL^T$.
My question is how to calculate $B^{-1}A$ ...
- 63
2
votes
0
answers
291
views
Computational complexity of the Cholesky factorization
According to the Cholesky factorization on Wikipedia, the computational complexity of it is $\frac{n^3}{3}$ FLOPs where $n$ is the size of the considered matrix $\mathbf{A}$.
There are various ...
- 356
0
votes
0
answers
57
views
When does a log-convex function not form an positive semi-definite matrix?
If we consider the function $f(x)$ and the matrix A formed as follows
$$
A_{ij} = f(\frac{x_i + x_j}{2})
$$
and state that $f(x)$ is log-convex and non-negative
$$
f(x_1)^tf(x_2)^{(1-t)} \geq f(tx_1 + ...
- 651
1
vote
1
answer
80
views
Every definite positive matrix admits Cholesky decomposition: help with Demmel's proof
I am studying Cholesky decomposition by using the book "Applied Numerical Linear Algebra" of Demmel. In particular, I am trying to understand why a positive definite matrix $A\in\mathbb{R}^{...
- 2,183
0
votes
0
answers
38
views
Prove that $\sum=CC^T\Rightarrow \sum^{-1}=C^TC$
For $\sum$ covariance matrix ($n\times n$, symmetric and positive definite) and $C$ lower triangular matrix with real and positive entries, how can I prove the equivalence as from title?
I know that ...
- 41
0
votes
0
answers
83
views
Reverse software engineering of "\" in Matlab
23.3 Reverse software engineering of "". The following Matlab session records a sequence of tests of the elapsed times for various computations on a workstation manufactured in 1991. For ...
2
votes
0
answers
58
views
Let $A$ be symmetric and positive definite. Suppose $A=LL^T$ is its Cholesky decomposition. Prove that $||A||_2=||L||_2^2$.
Let $A$ be symmetric and positive definite. Suppose $A=LL^T$ is its Cholesky decomposition. Prove that $||A||_2=||L||_2^2$.
This is an exercise in my Numerical Analysis book. The offcial hint to this ...
- 4,859
0
votes
3
answers
391
views
Cholesky factors of covariance and precision matrix
Let $\Sigma$ be a covariance matrix (symmetric positive-definite), and $\Omega = \Sigma^{-1}$ the corresponding precision matrix, which is also SPD (the quotients of positive eigenvalues are positive)....
- 2,085
0
votes
0
answers
44
views
Cholesky decomposition for PD matrix
Let $A=A^T$ be a $n\times n$ positive definite matrix. Define the numbers $f_i(A)=\min\{j:a_{ij}\neq 0\}.$ Consider the following Cholesky decomposition: $A=LL^T$, with $L$ being a lower triangular ...
- 89