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.

Filter by
Sorted by
Tagged with
0 votes
0 answers
9 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. ...
P. Quinton's user avatar
  • 5,944
1 vote
0 answers
34 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 ...
jlewk's user avatar
  • 1,915
2 votes
1 answer
50 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 ...
P. Quinton's user avatar
  • 5,944
1 vote
1 answer
52 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?
Jannis's user avatar
  • 153
2 votes
1 answer
32 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 ...
mins's user avatar
  • 385
1 vote
0 answers
38 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$ ...
bansed's user avatar
  • 11
0 votes
0 answers
35 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{...
mathoverflowUser's user avatar
0 votes
0 answers
12 views

SVD or Cholesky on sum of SPD matrices

Let $A$ and $B$ be symmetric positive definite (SPD) matrices and $C=A+B$. I know the SVD or Cholesky decomposition of A and B, $A=U_A\Sigma_AU_A^T=L_AL_A^T$ and $B=U_B\Sigma_BU_B^T=L_BL_B^T$. Can I ...
kampfkoloss's user avatar
0 votes
0 answers
11 views

Which row/column to remove from SPD matrix to remain maximal volume

Let $A$ be a real $N\times N$ symmetric, positive definite (SPD) matrix with volume $vol(A)=|det(A)|$. Let $B_i$ be the matrix $A$ where row and column $i$ were exchanged by a unit vector $e_i$. Can I ...
Yoke's user avatar
  • 1
0 votes
1 answer
63 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 (...
Alexlok's user avatar
  • 103
1 vote
1 answer
52 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-...
Jim Ferry's user avatar
  • 2,303
0 votes
0 answers
23 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 = ...
euraad's user avatar
  • 2,914
0 votes
1 answer
60 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 ...
euraad's user avatar
  • 2,914
0 votes
0 answers
21 views

Pivoted Cholesky - triangulate the resut?

I have implemented pivoted Cholesky from http://www.dfg-spp1324.de/download/preprints/preprint076.pdf. My expectation was that I would be able to use the resulting triangular matrix to easily solve ...
aquila's user avatar
  • 105
5 votes
1 answer
317 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 ...
daknowles's user avatar
  • 153
0 votes
0 answers
33 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 $...
Federico Collasius's user avatar
0 votes
0 answers
81 views

Generating Correlated Random Variable Samples with Copulas or with Choleski Decomposition?

Suppose I want N samples of X and Y, which are two random variables which are correlated with a certain value of correlation coefficient. They have generally non-gaussian PDF, but at the moment let's ...
Kinka-Byo's user avatar
  • 239
1 vote
0 answers
49 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)}...
Quasar's user avatar
  • 5,400
1 vote
0 answers
31 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 ...
A Varga's user avatar
  • 11
0 votes
0 answers
86 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 ...
Przemo's user avatar
  • 11.2k
1 vote
0 answers
179 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 ...
euraad's user avatar
  • 2,914
0 votes
1 answer
239 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. $\...
landau's user avatar
  • 11
1 vote
0 answers
127 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 ...
Smartis's user avatar
  • 11
2 votes
1 answer
298 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 \...
Sizhe Ding's user avatar
1 vote
1 answer
62 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 ...
Mario Palacios's user avatar
0 votes
1 answer
66 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 ...
ColinBroderick's user avatar
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 ...
Clarent's user avatar
  • 145
0 votes
0 answers
47 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? ...
JenJen's user avatar
  • 1
0 votes
0 answers
61 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$, ...
kampfkoloss's user avatar
-1 votes
1 answer
169 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.
riya's user avatar
  • 1
0 votes
1 answer
76 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 ...
Jeremy Weissmann's user avatar
0 votes
1 answer
46 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 ...
Oliver Mohr Bonometti's user avatar
2 votes
1 answer
171 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 ...
PC1's user avatar
  • 2,175
1 vote
1 answer
276 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 ...
Morcus's user avatar
  • 583
1 vote
1 answer
322 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 ...
Miss Mulan's user avatar
0 votes
0 answers
115 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 ...
Nadir BM's user avatar
3 votes
1 answer
644 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 ...
Ishigami's user avatar
  • 1,535
1 vote
3 answers
591 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 ...
kampfkoloss's user avatar
1 vote
0 answers
65 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{...
dhc's user avatar
  • 173
0 votes
1 answer
338 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 ...
user3180's user avatar
  • 707
0 votes
1 answer
23 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 ...
IHopeItWontBeAStupidQuestion's user avatar
0 votes
0 answers
109 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}...
engfrompalestine's user avatar
0 votes
1 answer
340 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 ...
Adam Wilson's user avatar
0 votes
0 answers
613 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....
math123's user avatar
  • 31
3 votes
1 answer
191 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)^\...
Josh Pilipovsky's user avatar
-1 votes
2 answers
548 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. ...
euraad's user avatar
  • 2,914
1 vote
1 answer
682 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 \...
clementine1001's user avatar
0 votes
1 answer
49 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://...
Amin's user avatar
  • 55
1 vote
0 answers
56 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, ...
Bruno Mello's user avatar
-1 votes
1 answer
122 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}.$...
Johndoe's user avatar
  • 527