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.
150 questions
-1
votes
0
answers
24
views
Cholesky decomposition iterative algorithm in the case a matrix is not PD [duplicate]
I am trying to implement a Python function to calculate the Cholesky decomposition of a square matrix $A$, when in the case the matrix is not PD I want to return a vector $v$ such that $v^T \cdot A \...
- 1
0
votes
1
answer
50
views
Efficient inversion of $A^T A + B^T B$
Consider matrices $A \in \mathbb R^{k \times n}, B(\eta) \in \mathbb R ^{l \times n}$, where $B$ depend on some parameters $\eta$. The matrix $A$ will be fixed.
My problem is to compute
$$
(A^TA + B(\...
2
votes
1
answer
30
views
About perturbation bound for Cholesky factorization
I recently met the following problem about controlling the difference between Cholesky factors of two matrices when studying a problem in terms of estimating Cholesky factors from data.
For two ...
- 55
0
votes
0
answers
36
views
Approximation to the Choleski decomposition of a matrix inverse
I have a matrix $\boldsymbol{Q} = \boldsymbol{I} + \alpha\cdot\boldsymbol{L}^T\boldsymbol{L}$ and I am looking for an (approximate) solution $\boldsymbol{A}$ to $$\boldsymbol{A}\boldsymbol{A}^T = \...
- 133
0
votes
1
answer
85
views
$LDL^T$ factorization and iterative refinement
I have to solve the system $Ax = b$ where $A$ is symmetric and positive semidefinite.
The following assumes that no floating-point arithmetic errors occur.
$A$ is factored using $LDL^T$ algorithm with ...
- 1
0
votes
0
answers
37
views
Speeding up Cholesky Decomposition in Gaussian Process Regression
I am currently working on a project that is pulling posterior samples from a Gaussian Process according to the following formula:
$Y(x) = \mu(x) + (\Sigma)^{1/2}\mathcal{Z}$
where $\mu(x)$ is a mean ...
0
votes
0
answers
47
views
On the condition of positive semidefiniteness of a matrix
According to Wikipedia,
$\textbf{Wikipedia definition:}$ an $n\times n$ Hermitian matrix $M$ is positive semidefinite if and only
if it can be decomposed as a product $M = BB^*$ where $*$ is the
...
- 406
0
votes
2
answers
51
views
What is the Cholesky decomposition of the sum of a diagonal and a matrix of ones?
What is the Cholesky decomposition $\mathbf{A}=\mathbf{L}\mathbf{L}^\intercal$ of the sum $\mathbf{A}=\mathbf{D}+\mathbf{1}$ of a diagonal matrix $\mathbf{D}$ with only positive elements in the ...
- 421
0
votes
0
answers
35
views
Cholesky factorization in L-BFGS-B
L-BFGS-B is one of the most used quasi-Newton solver and the original paper [1] is quite explicit about how to implement the algorithm. In one of the following paper [2], they detail the reference ...
- 113
1
vote
0
answers
12
views
Inertia of reduced symmetric real regular indefinite matrix
Given is a regular real symmetric matrix $\boldsymbol{A} \in \mathbb{R}^{n \times n}$, with $m < n/2$ negative eigenvalues.
I wish to know: Is it always possible to extract a submatrix of $k=n-2\...
- 21
0
votes
1
answer
97
views
Gradient with respect to $LDL^\prime$ parameterization of covariance matrix
I have been working with the matrix-variate normal distribution (a.k.a., matrix normal distribution) $\mathbf{X} \sim \text{Normal}_{nm}\big(\mathbf{M},\;\mathbf{I}_n,\mathbf{V}\big)$, such that (...
0
votes
0
answers
21
views
Endogeneity Analysis without the access of raw data?
I currently have the correlation/covariance matrix for a set of variables and the results of regression analysis but lack access to the raw dataset. Under these constraints, is it feasible to conduct ...
0
votes
0
answers
13
views
Factorizing $AMA^T+N=WW^T$ efficiently.
This question is related to this question with a slightly more general setting. A good speedup on this could improve performances of a decision process in multi-objective optimization that I designed.
...
- 6,032
1
vote
0
answers
35
views
Random bounded triangular $T_n$ s.t. $Var[T_nS_nT_n^\top]\to 0$ for nonrandom psd $S_n$. Does $(T_n-\bar T_n)S_n\to^P0$ for some nonradom $\bar T_n$?
Let $T_n$ be a sequence of square random matrices with $T_n$ lower triangular with $diag(T_n)=(1,1...,1)$ and $S_n$ a sequence of deterministic symmetric psd matrices. All matrices are in $R^{d\times ...
- 2,207
2
votes
1
answer
69
views
Cholesky factorization of $A M A^T$ for $M$ PSD with known Cholesky factorization.
In the context of my research, I am trying to efficiently compute/store a PSD matrix and the cholesky factorization might help.
Let $M\in\mathbb R^{n\times n}$ and $A\in\mathbb R^{m\times n}$ be such ...
- 6,032
1
vote
1
answer
56
views
Is the group $Lx+b$ amenable where $L$ is Cholesky?
Let $L$ be any real lower triangular matrix with positive diagonal entries (a Cholesky matrix). Let $x$ and $b$ be real vectors. Is the group of actions $(L, b)$ on $x$,
$$L x + b$$
amenable?
- 229
2
votes
1
answer
70
views
How can I use this Cholesky decomposition algorithm on this example?
In this course, the authors introduce a method for Cholesky decomposition of matrix $A$, based on row reduction:
Procedure 7.4.1: Finding the Cholesky Factorization
Using only type 3 elementary row ...
- 455
1
vote
0
answers
44
views
Most accurate way to multiply with inverse Cholesky decomposition
What is the most accurate way to compute $x^TA^{-1}y$ for two vectors $x$ and $y$, and a symmetric positive definite matrix $A$?
With a Cholesky decomposition $A=LL^T$, one could either apply both $L$ ...
- 11
1
vote
0
answers
41
views
Prime numbers and a positive definite matrix?
Probably this has nothing to do with prime numbers, I just experimented a little bit with it and wanted to share it, in case someone has an idea.
Let
$$p_n := n\text{-th prime number , }[a,b]:= \frac{...
- 710
0
votes
1
answer
224
views
Equivalence of the LDL decomposition with an upper-triangular or lower-triangular matrix
I am aware that given a positive-definite matrix $A$ we can compute its LDL decomposition as:
$$ A = L D L^t $$
where $L$ is a lower unit triangular matrix and $D$ a diagonal matrix.
In this paper by (...
- 103
1
vote
1
answer
75
views
Analog of Sherman–Morrison matrix inversion formula for $(A-bx^T)^T (A-bx^T)$
Let $A$ be a real $n \times d$ matrix, $\vec{b} \in \mathbb{R}^n$, and $\vec{x} \in \mathbb{R}^d$. I'd like to find a simple formula for$$
F(\vec{x}) = \left(\left(A-\vec{b}\vec{x}^T\right)^T \left(A-...
- 2,333
0
votes
0
answers
33
views
What's the difference between using the inverse trick VS cholesky trick for solving generalized eigenvalue problem?
My math professor said once that solving the generalized eigenvalue problem
$$A\lambda = \lambda B v$$
There are two methods to use:
Method #1
Use cholesky decomposition
$$B = LL^T$$
Solve $Y$
$$AY = ...
- 2,982
0
votes
1
answer
74
views
What's the best way to make a symmetric matrix positive definite?
Assume that you have a matrix $X \in \mathbb R^{m \times m}$ and it's symmetric, but it's not positive definite.
What's the best way to turn the matrix $X$ into a positive definite matrix?
I have a ...
- 2,982
5
votes
1
answer
349
views
Sparse Cholesky decomposition of factorized matrix
I want the diagonal of a matrix $Y^TA^{-1}Y$ where $A=X^TX$ and $X$ is very sparse with dimensions ~1e6 x ~1e5 (so $A$ is 1e5 by 1e5). $Y$ is something like 1e5 by 1e4 (also sparse). Currently I'm ...
- 153
0
votes
0
answers
42
views
Product of Different Diagonal Entries in Positive Definite Matrix Exceeds Product of Different Off-Diagonal Entries.
I am currently battling with a problem involving positive definite matrices and I would greatly appreciate some assistance.
Let $A$ be a positive definite, though not necessarily symmetric, matrix in $...
1
vote
0
answers
80
views
Cholesky factorization using Gram-Schmidt
I am trying to find the Cholesky factorization $AA^T$ of the below covariance matrix $C$, to decompose a gaussian vector into independent standard normal random variables. However, the entry $a_{(3,3)}...
- 5,594
1
vote
0
answers
38
views
Computation of smooth Cholesky factorizations
Assume $X(t)$ is a time dependent positive definite symmetric matrix which satisfies the matrix differential equation
$\dot{X}(t) = Q(X(t)), X(0) = 0, $
where $Q(X(t))$ is a symmetric positive ...
- 11
0
votes
0
answers
111
views
How to check whether a tensor is completely symmetric?
Let $N\ge 2$ be an integer. Let $C:= \left( C_{i,j} \right)_{i,j=1}^N$ be a symmetric and positively definite matrix. Then there exists another matrix ${\tilde C}$, which is lower-diagonal, and such ...
- 11.8k
1
vote
0
answers
274
views
How to I solve Generalized Eigenvalue Problem with Cholesky Factorization if $A$ and $B$ are symmetrical?
Assume that we are going to solve generalized eigenvalue problem
$$Av = \lambda B v$$
Where $A$ and $B$ are symmetrical matrices.
Assume that we can only use the MATLAB routine ...
- 2,982
1
vote
1
answer
332
views
Fast shortcut to get the Cholesky factor of a submatrix
Assumptions
Let's start with the following assumptions. Assume the matrices $\Sigma$, $L$, and $S$ defined below are known in advance.
$\Sigma$ is a symmetric positive definite $n \times n$ matrix.
$\...
- 21
1
vote
0
answers
240
views
Schur complement of the marginalized normal covariance matrix given joint Cholesky decomposition
Consider a multivariate normal distribution with covariance matrix $\Sigma$ of size $n \times n$, which can be written in terms of its lower triangular Cholesky decomposition $L$ as
$$\Sigma = L \cdot ...
- 11
2
votes
1
answer
495
views
Condition number change in Cholesky matrix decomposition [closed]
Give a symmetric positive definite matrix $A$ that has a LDLT decomposition $A = L D L^{\top}$, why is the condition number of $A$ not less than that of matrix $D$, i.e., $\mbox{cond} (A) \geqslant \...
- 71
2
votes
1
answer
81
views
Doubt about Bulirsch's proof for Cholesky decomposition.
I was reading the Bulirsch and Stoer's Introduction to Numerical Analysis proof for the Cholesky decomposition, you can find a copy here, and I got stuck.
My problem is that, in my opinion, there's a ...
0
votes
1
answer
114
views
How can we prove that the Cholesky decomposition of an ellipsoid transforms that ellipsoid onto the unit sphere
Say I have a collection of points $x_i$ that define the surface of a fully general ellipsoid in three dimensions, except let's assume that ellipsoid is centered at the origin. I know that the ...
0
votes
0
answers
31
views
If $A\succ B\succ 0$ for $A,B$, then is $\| Ax\|_2 \ge \| Bx\|_2$?
I'm trying to prove the following statement, which really feels like it should be correct.
If $A\succ B \succ 0$ for symmetric $A,B$, then show that $||Ax||_2 \ge || Bx||_2$ for vector $x$.
The ...
- 141
0
votes
0
answers
49
views
How to find the $LU$ representation of a non-symmetric matrix?
I have a $3\times4$ matrix $A$, and I have to find matrices $L$ and $U$, such, that $A=LU$. But the problem is that the matrix is not symmetric, and I get a lot of variables. Any methods to do this?
...
- 1
0
votes
0
answers
64
views
Cholesky decomposition of matrix product, $A=BB^T$, where $B\in \mathbb{R}^{n\times m}$ [duplicate]
Assume $A=BB^T$, where $B\in \mathbb{R}^{n\times m}$ and therefore $A\in \mathbb{R}^{n\times n}$. The product $A$ is always symmetric positive definite. I want to find the Cholesky factor $A=LL^T$, ...
- 21
-1
votes
1
answer
218
views
Cholesky decomposition how to prove
From calculation of the Cholesky decomposition of covariance matrix, prove whether a symmetric matrix being positive or not can be determined from signs of principal diagonal minors.
- 1
0
votes
1
answer
92
views
LDU and principal minors of symmetric positive definite matrix
Suppose $A$ is an $n\times n$ symmetric positive definite matrix. We know that $A$'s leading principal minors $m_1,m_2,\dots,m_n$ are positive.
Now suppose that $A$ has LDU decomposition $A=LDU$, and ...
- 431
0
votes
1
answer
54
views
Create correlated random numbers with specified mean and standard deviation
I have two series of numbers that have certain correlation coefficient $\rho$.
How can I make a two series of random numbers that have correlation $\rho$, $\mu = 0$ and $\sigma = 1$?
I tried using ...
2
votes
1
answer
218
views
Cholesky inverse
I have the Cholesky decomposition $LL^T$ of a symmetric positive definite matrix. I then compute a result in the form of $A=LXL^T$, where $A$ and $X$ are also symmetric positive definite matrices.
I ...
- 2,196
1
vote
1
answer
458
views
Relationship between the eigenvalues of a matrix and its Cholesky decomposition
Cholesky decomposition states that if $A$ is symmetric positive semidefinite matrix , then there exists a lower triangular matrix $L$ with nonnegtive diagonal elements such that
$$ A = LL^T $$
Is ...
- 615
1
vote
1
answer
451
views
Cholesky decomposition of a strictly diagonaly dominant symmetric matrix
I am studying for a exam and I thought about practicing the Cholesky decomposition.
If a matrix $A = A^{T}$ , the main diagonal of $A$ has only positive elements and in every row the absolute value of ...
- 189
0
votes
0
answers
135
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
3
votes
1
answer
1k
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 ...
- 2,058
1
vote
3
answers
1k
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 ...
- 21
1
vote
0
answers
76
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{...
- 173
0
votes
1
answer
577
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 ...
- 739
0
votes
1
answer
25
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
124
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}...
