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
0answers
11 views

What is the diagonal entries of Schur complements?

Given that A is SPD, its Schur complement should also be SPD. I have a wild guess that the diagonal elements of the Schur complement equals to the square of the diagonal elements of the same entries ...
0
votes
0answers
22 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$ ...
1
vote
0answers
31 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 ...
0
votes
0answers
20 views

Solving Linear System with partly given Cholesky Decomposition

I want to solve a linear system given by a Least Squares Support Vector Machine: $$\left[\begin{array}{cc} 0 &-Y^T \\ Y & \Omega + \gamma^{-1}I \end{array}\right]\left[\begin{array}{c} b\\ \...
0
votes
0answers
42 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 + ...
1
vote
1answer
24 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}^{...
0
votes
0answers
29 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 ...
0
votes
0answers
36 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
0answers
27 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 ...
0
votes
3answers
64 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)....
0
votes
0answers
30 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 ...
0
votes
0answers
25 views

Generating non-normal correlated random variables with Cholesky decomposition

The Cholesky decomposition of the correlation matrix, $C$, can be used to generate correlated random variables, $Y=LX$, from uncorrelated variables $X$, if $LL^{T}=C$, and if (for two correlated ...
0
votes
0answers
18 views

Cholesky Factorization: Last Element of the Inverse

Given $A=R^{T}R$ which is a Cholesky Factorization, need to prove: $$ A^{-1}_{n,n}=r_{n,n}^{-2} $$ where $(n,n)$ is the element in nth row and nth column and $r$ is element in $R$. Not sure how to go ...
1
vote
1answer
41 views

Matrix inverse identity with Cholesky decomposition

I need some help to prove the following formula: $(c \cdot P^{-1} + X \cdot X^T)^{-1}=L\cdot(c \cdot I_n + L^T \cdot X \cdot X^T \cdot L)^{-1}\cdot L^T$ The matrix $X$ has dimension $n \times N$ ...
1
vote
1answer
50 views

How can I show from $AA'=PP'=C$ that $A$ is an orthonormal transformation of $P$?

Problem details $P$ is the lower triangular Cholesky factor of the positive semidefinite matrix $C$ ($PP'=C$) $A$ is any matrix such that $AA'=C$ How can I show that $A$ is an orthonormal ...
0
votes
1answer
39 views

Show that those matrices are similar

I need a check on the following problem: Let us consider the following algorithm: $B_0$ given, SPD matrix. Compute its Cholesky factorization $B_k = L_k L_k^T $, for $k=0,\ldots$ Define $B_{k+1} = ...
3
votes
1answer
67 views

In the Cholesky decomposition, the argument of the square root is always positive if the matrix is real and positive definite. Why?

Computing the Cholesky decomposition for an $n \times n$ matrix $A$ you need to evaluate $$l_{jj} = \sqrt{a_{jj}-\sum_{k=1}^{j-1} l^2_{jk}}$$ The argument of the square root is always positive if $A$ ...
2
votes
1answer
43 views

Show that the eigenvalues of $L^{-1}AL^{-T}$ are clustered around 1 when $R$ is small where $L, L^{T}$ are incomplete Cholesky factors.

The incomplete Cholesky factorisation of a $A$ is $A = LL^T + R$ where $R$ is the remainder and the sparsity pattern of $L$ is the sparsity pattern of lower triangular part of $A$. I need to show that ...
0
votes
1answer
75 views

Derivative of vectorized function wrt to a Cholesky decompositiion

Let $\Sigma$ be a symmetric, positive definite $p\times p$ covariance matrix, and let $f(\Sigma)$ be it's Cholesky factor. That is, $f(\Sigma)$ is a lower triangular $p\times p$ matrix such that $\...
0
votes
0answers
28 views

Redundant sigma points in Unscented Kalman Filter?

According to the Unscented Transform equations in an Unscented Kalman Filter, sigma points are chosen via: $\chi^{[0]}=\mu$ $\chi^{[i]}=\mu+\left(\sqrt{(n+\lambda)\Sigma}\right)_i\;\;\;i=1,...,n$ $\...
1
vote
2answers
51 views

For which values the matrix $ B = \Big(\begin{matrix} A & -A\\ -A & \alpha A \end{matrix}\Big)$ results positive definite (strict)?

I'm trying to solve the next problem where given $A \in \mathbb{R}^{n \times n}$ symmetric positive definite I have to find the values for $\alpha \in \mathbb{R}$ such that this matrix: $ B = \Big(\...
0
votes
1answer
104 views

Cholesky decomposition of a Kronecker product

Assume that the $n\times n$ matrix $\mathbf{A}$ has the Cholesky decomposition of the form $\mathbf{A}=\mathbf{L}\mathbf{L}^H$. Now, suppose the matrix $\mathbf{B}$ is the result of a Kronecker ...
0
votes
1answer
42 views

Prove that $\|R\|_2 = \|A\|_2^{1/2}$ where $A=R^* R$ is a Cholesky factorization of $A$

Prove that $\|R\|_2 = \|A\|_2^{1/2}$ where $A = R^* R$ is a Cholesky factorization of $A$. In my book it says that I should use the Singular Value Decomposition. I have that $\rho(A)=\sqrt{\rho(A^*A)}=...
1
vote
1answer
81 views

Is a symmetric matrix $A = LDL^T$ positive definite if D contains 2x2 blocks?

A symmetric matrix $A = LDL^T$ is positive definite if $D$ is diagonal with strictly positive elements. What about the case where $D$ is block-diagonal: what would be the condition for positive-...
0
votes
1answer
42 views

Generating two correlated random numbers: Why does volatility be 1 by using Cholesky decomposition?

I am trying to use Cholesky decomposition to generate two correlated random numbers by simulating two uncorrelation distributions. The covariance matrix should be $$ C= \left[\begin{matrix} \...
0
votes
1answer
12 views

Generating symmetric Positive Definite Matrix from random vector multiplication yield singular matrix

This might seem a very naive or ignorant question, but I am not able to give myself a satisfactory explanation. Suppose i want to generate a random symmetric positive definite matrix. I was under the ...
0
votes
0answers
26 views

How can we take use Cholesky factorization to show that a given symmetric matrix, M is positive semi-definite?

Let's discard the fact that we know anything about the eigenvalues of being real and positive. Can we still prove a symmetric matrix to be semi-definite? What should be its properties? I have a matrix,...
-1
votes
1answer
59 views

If A positive definite then $\lvert\det(A)| \leq \prod_{i=1}^n \Vert a_{i}\Vert$

I've asked a similar problem earlier here and I was told the same is true for $\lvert\det(A)| \leq \prod_{i=1}^n \Vert a_{i}\Vert$ with $\Vert a_{i,i}\Vert$ being the norm induced by the Euclidean ...
0
votes
1answer
29 views

Positive- definiteness of factors of Cholesky factorization

If A is a symmetric positive-definite n×n matrix, then is the lower triangular n×n matrix L positive-definite when A=LL* using Cholesky factorization?
3
votes
1answer
82 views

Is a symmetric matrix positive definite iff $D$ in its LDU decomposition is positive definite?

Given $$A=LDU$$ where $A$ is a real symmetric matrix $L$ is a lower unitriangular matrix $D$ is a diagonal matrix $U$ is an upper unitriangular matrix can we say that $$A>0 \iff D>0$$ ? Edit:...
0
votes
2answers
231 views

Determining whether a matrix is positive definite from its LU decomposition

Given that $A=LU$ where $L$ and $U$ are (known) lower and upper triangular matrices, is there any simple way to determine whether $A$ is positive definite? Background I have been using this algorithm ...
0
votes
1answer
42 views

Show that $A$ is positive definite via the Cholesky decomposition

I have calculated the Cholesky decomposition of the matrix \begin{equation*}A=\begin{pmatrix}1 & -1 & -1 & 0 \\ -1 & 5 & 5 & -4 \\ -1 & 5 & 6 & -3 \\ 0 & -4 &...
0
votes
0answers
19 views

Accepted notation for solving systems of linear equations using Cholesky factors

To avoid explicit matrix inversions, some code I am writing formal documentation for frequently solves systems of equations of the form $A x = b$ for $x$ given symmetrical $A$, for example to ...
0
votes
1answer
31 views

Cholesky decomposition for special structure matrix

Suppose the matrix is of the form $\tilde{A} = aI -A^TA$, where $I$ is the identity matrix and $a>eig(A^TA)$. Assume that Cholesky decomposition is possible. Do we get a nice analytic expression or ...
0
votes
1answer
160 views

Cholesky decomposition of tensor product

Let $A\in\mathbb R^{n\times n}$, $B\in\mathbb R^{m\times m}$ be symmetric, positive definite, matrices. Let $C = A\otimes B$ be their tensor product. I want to compute the Cholesky decomposition of $C$...
1
vote
0answers
74 views

Eigenvalues using cholesky factors

When a matrix $A_0$, for example $2 \times 2$ matrix, is symmetric positive definite, the following steps can compute the eigenvalues of $A_0$, $A_k=R^T_k R_k$ (Cholesky Decomposition) $A_{k+1}=R_k ...
3
votes
0answers
107 views

Cholesky of a submatrix

I have a large-ish matrix that is the Kronecker product of two smaller matrices $V = A \otimes B$. A and B are both positive definite. I want to take the Cholesky decomposition of arbitrary subsets ...
0
votes
1answer
607 views

Cholesky decomposition for $AA^t$

Assuming a given matrix is of the form $A^TA$, where $A$ is a real matrix of full rank, $A^TA$ is a positive definite matrix and we can write its Cholesky decomposition. Is there a more efficient ...
9
votes
1answer
8k views

How to prove the existence and uniqueness of Cholesky decomposition?

Given a real Hermitian positive-definite matrix $A$ is a decomposition of the form $A=L L^T$ where L is a lower triangular matrix with positive diagonal entries. I read some proofs about the existence ...
9
votes
2answers
8k views

Generating multivariate normal samples - why Cholesky?

Hello everyone and happy new year! May all your hopes and aspirations come true and the forces of evil be confused and disoriented on the way to your house. With that out of the way... I am trying ...
25
votes
2answers
11k views

LU Decomposition vs. Cholesky Decomposition

What is the difference between LU Decomposition and Cholesky Decomposition about using these methods to solving linear equation systems? Could you explain the difference with a simple example? Also ...
11
votes
2answers
2k views

Inverse of the sum of a invertible matrix with known Cholesky-decomposion and diagonal matrix

I want to ask a question about invertible matrix. Suppose there is a $n\times n$ symmetric and invertible matrix $M$, and we know its Cholesky decomposion as $M=LL'$. Then do we have an efficient way ...
0
votes
1answer
36 views

Preferred matrix decomposition

Consider a complex square matrix $A\in\mathcal{C}^{n\times n}$. Now let us discuss two kinds of the factorization of $A$, say, eigendecomposition and Schur decomposition because both of them are often ...
7
votes
0answers
989 views

Can I go from the LU factorization of a symmetric matrix to its Cholesky factorization, without starting over?

I mistakenly computed the LU factorization and then realized that the question is asking for a Cholesky factorization, i.e., finding a lower triangular matrix L such that the symmetric matrix A has ...
3
votes
1answer
266 views

Proving that $L_{22}L_{22}^T=S$ is the Schur complement of a Cholesky factorization

Let $A$ be an $(n+m) \times (n+m)$ symmetric positive definite matrix $$A=\begin{bmatrix}A_{11} & A_{12}\\ A_{12}^T & A_{22}\end{bmatrix}$$ where $A_{11}$ is an $n \times n$ matrix, $A_{12}$ ...
0
votes
1answer
446 views

QR and Cholesky decomposition

A while ago I asked for help to develop a polynomial regression model using least squares, where the system was solved by cholesky decomposition, you can check it here Cholesky Polynomial Regression ...
1
vote
1answer
1k views

Cholesky algorithm

Good afternoon everyone, I'm in need of a factoring algorithm cholesky and algorithms to solve upper and lower triangular systems, but I'm not finding any work in that octave. Recalling that need the ...
14
votes
1answer
3k views

Cholesky of matrix plus identity

I have a positive definite matrix $A$ ($n \times n$ dimension) for which I have the Cholesky decomposition $A=LL^{'}$. I want to use this to compute a) The Cholesky decomposition of $A+c^2\times I $ ...
0
votes
1answer
338 views

Diagonally dominant matrix for Cholesky?

I have a $10^6 \times 10^6$ dense SPD matrix, which I am called to invert, by using Cholesky factorization. However, I came across this statement: We start with the Cholesky and LU decompositions, ...
0
votes
1answer
114 views

Cholesky factorization exist?

Is there a theorem or a way to show that if I have a real and symmetric positive definite matrix $A$ and its Cholesky factorization is $A = LL^T$ then $B = L^TL$ is also positive definite? Or in other ...