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.
72
questions
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 ...