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
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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{...
user avatar
  • 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 ...
user avatar
  • 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,...
user avatar
  • 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 ...
user avatar
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}...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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....
user avatar
  • 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)^\...
user avatar
-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. ...
user avatar
  • 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 \...
user avatar
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://...
user avatar
  • 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 $\...
user avatar
  • 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, ...
user avatar
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, ...
user avatar
-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}.$...
user avatar
  • 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\...
user avatar
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 \...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 $...
user avatar
  • 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, ...
user avatar
  • 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 ...
user avatar
  • 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 = \...
user avatar
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 ...
user avatar
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 ...
user avatar
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 $$ \...
user avatar
  • 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 ...
user avatar
  • 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!
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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. ...
user avatar
  • 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, ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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: $...
user avatar
  • 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}$ ...
user avatar
  • 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 ...
user avatar
  • 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$ ...
user avatar
  • 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 ...
user avatar
  • 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 + ...
user avatar
  • 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}^{...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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)....
user avatar
  • 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 ...
user avatar
  • 89