Positive definite?

This topic is 3618 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

Recommended Posts

Given an MxN matrix A, B = (A^T A) will be an NxN matrix. Will there exist a Cholesky decomposition for B, B = LL^T ?

Share on other sites
Of course in general the answer is no (the easiest case to think about is A being full of zeros), but in reality it depends on the possible values in A. I don't know the details of your application but you could just check for positive eigenvalues. Also note that the Cholesky decomposition is LL* - conjugate transpose instead of regular transpose. If you have imaginary numbers in there, then you will have problems with regular transpose.

Share on other sites
I forgot to mention that A is real, so the conjugate transpose is the transpose.
The matrix A contains a bunch of partial derivatives (essentially a Jacobian). I could generate the eigenvalues and check, but that only tells me for a specific matrix...I'm trying to find out under what general circumstances I can assume that it will be positive definite.

From Wikipedia,

"Systems of the form Ax = b with A symmetric and positive definite arise quite often in applications. For instance, the normal equations in linear least squares problems are of this form. It may also happen that matrix A comes from an energy functional which must be positive from physical considerations; this happens frequently in the numerical solution of partial differential equations."

http://en.wikipedia.org/wiki/Cholesky_decomposition

Clearly somebody was able to make a general statement that "the normal equations in linear least squares problems are positive definite"....but my question is, how do they know this? What physical constraints make this true? They haven't really specified what a "normal equation" is.

Share on other sites
Did some more digging..

So, I found out what is meant by the normal equations. Also, it gives an interesting hint, saying that positive definite === full rank,

Quote:
 If the matrix \mathbf{X^TX} is well-conditioned and positive definite, that is, it has full rank, the normal equations can be solved directly by using the Cholesky decomposition...

http://en.wikipedia.org/wiki/Linear_least_squares

Having full rank is a lot easier to understand than some arbitrary funk about the eigenvectors.

Now by the definition of Cholesky,

Quote:
 However, if A is symmetric and positive definite, we can choose the factors such that U is the transpose of L; this is the Cholesky decomposition.

http://en.wikipedia.org/wiki/Cholesky_decomposition

And from the definition of positive definite,

Quote:
 For any matrix A, the matrix A*A is positive semidefinite, and rank(A) = rank(A*A). Conversely, any positive semidefinite matrix M can be written as M = A*A; this is the Cholesky decomposition. (contradiction??)

http://en.wikipedia.org/wiki/Positive-definite_matrix

Well, in the case I described above, the matrix is obviously positive semidefinite -- as are the normal equations. But this does not seem to make it positive DEFINITE, and that seems to be what Cholesky is defined upon. It seems that the last quote is a contradiction...

1. 1
2. 2
Rutin
22
3. 3
A4L
15
4. 4
5. 5
khawk
14

• 13
• 26
• 10
• 11
• 44
• Forum Statistics

• Total Topics
633742
• Total Posts
3013639
×