undefined | Better HN

0 pointsogogmad4y ago0 comments

> It is clear that you mean the ellipsoid as a set of points {x | x^T * A * x = 1} (or some other constant). There is another way in which all square matrices define an ellipsoid based on how the matrix transforms a unit sphere: {A*x | x^T * x = 1} (different matrices can map to the same ellipse here, however).

I actually had the latter one in mind: The one given by {A*x | x^T * x = 1}. I hadn't thought of your other suggestion.

> (I unfortunately do not have intuition for the QR algorithm, but I am distracted by the description of an ellipse falling, as if it's rolling against the x-axis)

I don't know if this helps: https://ibb.co/DRDLzgJ

Each iteration causes it to rotate around the origin. The big semi-axis of the ellipse makes a smaller angle with the x-axis on each iteration. When the semi-axes are parallel to the coordinate axes, the matrix is diagonal.

0 comments

gugagore4y ago

> I actually had the latter one in mind: The one given by {Ax | x^T x = 1}.

I am near certain that you did not mean this.

> When the semi-axes are parallel to the coordinate axes, the matrix is diagonal.

Let D =

the matrix

  | 2 0 | 
  | 0 1 |

And let R be any 2-by-2 rotation matrix.

A = D * R would give you a locus of points (under {Ax | x^T x = 1}) that has the semi-axes parallel to the coordinate axes. In general, A is not diagonal.

For the condition you mention (axis-aligned semi-axes of ellipsoid iff matrix is diagonal) is true for {x | x^T * A * x = 1} .

ogogmadOP4y ago

I only consider positive semi-definite symmetric matrices. A = D * R is almost certainly not such a matrix. The positive semi-definite symmetric case is the only one needed to compute SVDs.

A proof of convergence for the algorithm is only known for certain families of matrices. These include the positive-definite symmetric matrices, all symmetric matrices (once suitable improvements to the algorithm are made), the Hermitian matrices, and perhaps some others. But a proof that's valid for all matrices isn't known, even though the algorithm (when improved using Wilkinson shifts) appears to converge everywhere.

gugagore4y ago

Ah, okay. Sure. And PSD matrix A is diagonalizeable with orthogonal matrices i.e.

  A = Q^T * D * Q

The ellipsoid visualization you meant is insensitive to the Q term (any rotation of a sphere is the same sphere), but not to the Q^T term.

What I am still failing to understand is this sentence from the article:

> The basic QR algorithm can be visualized in the case where A is a positive-definite symmetric matrix.

It sounds like you can visualize the iterates A_{k} no matter what. Is the problem that there isn't a fixed point when the ellipsoid is axis-aligned?

The article has:

> Under certain conditions,[4] the matrices Ak converge to a triangular matrix, the Schur form of A.

So am I to understand that for A positive semi-definite, the A_{k} converges to a diagonal matrix?

1 more reply

j / k navigate · click thread line to collapse

0 pointsogogmad4y ago0 comments

I actually had the latter one in mind: The one given by {A*x | x^T * x = 1}. I hadn't thought of your other suggestion.

> (I unfortunately do not have intuition for the QR algorithm, but I am distracted by the description of an ellipse falling, as if it's rolling against the x-axis)

I don't know if this helps: https://ibb.co/DRDLzgJ

0 comments

gugagore4y ago

> I actually had the latter one in mind: The one given by {Ax | x^T x = 1}.

I am near certain that you did not mean this.

> When the semi-axes are parallel to the coordinate axes, the matrix is diagonal.

Let D =

the matrix

  | 2 0 | 
  | 0 1 |

And let R be any 2-by-2 rotation matrix.

A = D * R would give you a locus of points (under {Ax | x^T x = 1}) that has the semi-axes parallel to the coordinate axes. In general, A is not diagonal.

For the condition you mention (axis-aligned semi-axes of ellipsoid iff matrix is diagonal) is true for {x | x^T * A * x = 1} .

ogogmadOP4y ago

I only consider positive semi-definite symmetric matrices. A = D * R is almost certainly not such a matrix. The positive semi-definite symmetric case is the only one needed to compute SVDs.

gugagore4y ago

Ah, okay. Sure. And PSD matrix A is diagonalizeable with orthogonal matrices i.e.

  A = Q^T * D * Q

The ellipsoid visualization you meant is insensitive to the Q term (any rotation of a sphere is the same sphere), but not to the Q^T term.

What I am still failing to understand is this sentence from the article:

> The basic QR algorithm can be visualized in the case where A is a positive-definite symmetric matrix.

It sounds like you can visualize the iterates A_{k} no matter what. Is the problem that there isn't a fixed point when the ellipsoid is axis-aligned?

The article has:

> Under certain conditions,[4] the matrices Ak converge to a triangular matrix, the Schur form of A.

So am I to understand that for A positive semi-definite, the A_{k} converges to a diagonal matrix?

1 more reply

j / k navigate · click thread line to collapse