Linear Algebra 101 — Part 8: Positive Definite Matrix
Today, we are continuing to study the Positive Definite Matrix a little bit more in-depth. More specifically, we will learn how to determine if a matrix is positive definite or not. Also, we will learn the geometric interpretation of such positive definiteness which is really useful in machine learning when it comes to understanding optimization.
Just in case if you missed the last story talking about the definition of Positive Definite Matrix, you can check it out from below.
Materials covered in this story:
- Tests to check Positive Definiteness
- What is Quadratic form and how it can be used to check positive definiteness
- Geometric interpretation of positive definiteness
- How to make a positive definite matrix with a matrix that’s not symmetric
For the materials and structures, I’m following the famous and wonderful lectures from Dr. Gilbert Strang from MIT and you could see his lecture on today’s topic from Lecture 27
Ok, enough said, let’s get started.
Tests to check Positive Definiteness
Let’s say you have a matrix in front of you and want to determine if the matrix is positive definite or not. This will help you solve optimization problems, decompose the matrix into a more simplified matrix, etc (I will cover these applications later).
Based on the previous story, you had to check 3 conditions based on the definition:
The matrix has to be
- 1) symmetric
- 2) all eigenvalues are positive
- 3) all the subdeterminants are also positive
You could definitely check one by one for sure, but apparently, there’s an easier and practical way of checking this. And that’s the 4th way.
And this has to do with something called “quadratic form”.
What is Quadratic form and how it can be used to check positive definiteness
First, let’s define and check what’s a quadratic form is.
You should already know the quadratic form unrolled into an equation and above is just another way of representing it in linear algebra way.
So to show that it’s essentially the same thing, let’s try to write the quadratic form in matrix form to what you have seen before.
Not that difficult, hey?
To check if the matrix is positive definite or not, you just have to compute the above quadratic form and check if the value is positive or not.
What happens if it’s = 0 or negative?
That’s actually a good question and based on the signs of the quadratic form, you could classify the definiteness into 3 categories:
- Positive definite if (Quadratic form) > 0
- Positive semi-definite if (Quadratic form) ≥ 0
- Negative definite if (Quadratic form) < 0
Geometric interpretation of positive definiteness
Let’s try to make the concept of positive definiteness by understanding its meaning from a geometric perspective.
Remember I was talking about this definiteness is useful when it comes to understanding machine learning optimizations?
This is because the positive definiteness could tell us about the “plane” of the matrix.
If you are familiar with machine learning optimizations, you should know that the whole purpose of the machine learning is to tune the weights so that the loss becomes minimum.
The loss could be anything, but just to give you an example, think of a mean squared error (MSE) between the target value (y) and your predicted value (y_hat). You want to minimize the error between those two values so that your prediction is close to the target, meaning you have a good model that could give you a fairly good prediction.
To do this, there are various optimization algorithms to tune your weights. One of the most basic, but still used technique is stochastic gradient descent (SGD).
With SGD, you are going to calculate the gradient of the loss (e.g. MSE) and use it as a guide (direction) to go down the slope of an optimization plane to reach the bottom of the plane. Bottom of the plane basically indicated the lowest possible point in the loss, meaning your prediction is at the optimal point giving you the least possible error between the target value and your prediction.
However, the plane could have a different shape and a few simple examples is the following.
If the matrix is positive definite, then it’s great because you are guaranteed to have the minimum point. But the problem comes in when your matrix is positive semi-definite like in the second example. It has a somewhat stable point called a saddle point, but most of the time it just slips off the saddle point to keep going down to the hell where optimization becomes challenging.
As an exercise, you could also try thinking of what happens when the matrix is negative definite and what happens if you try to optimize for such case.
To give you a concrete example of the positive definiteness, let’s check a simple 2 x 2 matrix example.
Now the question is to find if the function “f” is positive for all x except its zeros.
To give you an example, one case could be the following.
You could try it yourself. Come up with any x1 and x2 that each satisfies the following. Try some other equations and see how it turns out when you feed the values into the quadratic function.
How to make a positive definite matrix with a matrix that’s not symmetric
So by now, I hope you have understood some advantages of a positive definite matrix.
The problem is, most of the time, a matrix is not always symmetric, to begin with. Could we possibly make use of positive definiteness when the matrix is not symmetric?
The answer is Yes!
You could simply multiply the matrix that’s not symmetric by its transpose and the product will become symmetric, square, and positive definite!
Summary
To summarize:
- Tests to check Positive Definiteness
Just calculate the quadratic form and check its positiveness.
- What is Quadratic form and how it can be used to check positive definiteness
If the quadratic form is > 0, then it’s positive definite.
If the quadratic form is ≥ 0, then it’s positive semi-definite.
If the quadratic form is < 0, then it’s negative definite.
- Geometric interpretation of positive definiteness
Positive definite is a bowl-shaped surface. Positive semi-definite is a saddle.
- How to make a positive definite matrix with a matrix that’s not symmetric
Just multiply by its own transpose.
I hope this helps! See you next time!
