The right way to Optimally Lure Factors in Excessive-Dimensional Areas Inside Ellipsoids

On this submit we research how you can lure a set of factors in excessive dimensions inside an ellipsoid with minimal quantity (John, 1948). This downside has functions in statistics and outlier detection, however my motivation for finding out this downside is to have the ability to signify “uncertainty units” for doing Strong Optimization. Please see this post if the phrases “uncertainty units” and Strong Optimization are new to you, if all you care is about studying geometry and optimization simply preserve studying.

Pictorially, what I’m attempting to do is, discover a description of the ellipsoid proven within the image beneath.

This submit is organized as follows, first I’ll present how you can concisely signify/describe ellipsoids utilizing matrices, then I’ll current another parametrization of ellipsoids that’s helpful for coming into the issue right into a solver. Lastly I’ll pose the Minimal Quantity Enclosing Ellipsoid (MVEE) downside as a convex optimization downside.

Earlier than we focus on ellipsoids lets get comfy describing their easiest kind, unit balls. You in all probability bear in mind from college that in two dimensions the ball of radius 1, might be represented because the set of all factors $x_1, x_2$ such that

$x_1^2 + x_2^2 leq 1.$

That’s the two-dimensional unit ball is $mathcal{B}_2 = lbrace x_1, x_2 in mathbb{R}: x_1^2 + x_2^2 leq 1 rbrace$. In $n$ dimensions, we’ve

$x_1^2 + x_2^2+ … + x_n^2 leq 1.$

It’s annoying to work with these giant equations so, if $x in mathbb{R}^n$ is is the column vector with entries $x_1, x_2, …, x_n$ we are able to merely write $mathcal{B}_n = lbrace x in mathbb{R}^n: x^prime x leq 1 rbrace$.

Nice, now, to go from a unit ball to an ellipsoid (lets give attention to ellipsoids centered across the origin) all we’ve to do is “squish it” and rotate it. A good way to signify, squishing and rotating a set of factors is thru making use of linear features of the shape $f(x) = Ax$ the place $A$ is an $n$ by $n$ matrix. For instance, think about making use of stress to the highest of the unit ball so it now not reaches 1 however as a substitute it solely reaches .5 (holding its width fixed), after which rotating counterclockwise 45 levels. This transformation is equal to first sending the unit vector pointing upwards from $[0; 1]$ to $[0; .5]$, then the 45 diploma rotation sends $[1; 0] rightarrow [frac{1}{sqrt{2}}; frac{1}{sqrt{2}}]$ and $[0; .5] rightarrow [-frac{1}{2sqrt{2}} ; frac{1}{2sqrt{2}}]$. The matrix that represents this transformation is

$A = start{bmatrix} frac{1}{sqrt{2}} & -frac{1}{2sqrt{2}} frac{1}{sqrt{2}} & frac{1}{2sqrt{2}} finish{bmatrix}.$

That’s proper, the primary column of the matrix tells you the place the unit vector $[1; 0]$ will get mapped to, and the second column tells you the place the opposite unit vector $[0; 1]$ will get mapped to. The earlier just isn’t a coincidence, by the way in which, when you really feel like digging deeper into why that is true I extremely advocate this post from Gregory Gundersen’s weblog, which I’ve clearly drawn inspiration (and template recordsdata (along with his permission)) from.

So, our ellipse $mathcal{E}$ is the set of all factors $y$ such that $y = Ax$ the place $x$ is within the unit ball. Since we’re desirous about “full dimensional” ellipsoids in $mathbb{R}^n$, that’s we’re not desirous about representing a 2-d circle in three-D house, the matrix $A$ is assumed to be invertible. Extra formally our ellipsoid is

$mathcal{E} = lbrace y in mathbb{R}^n, exists x mathbb{R}^n: y = Ax, x^prime x leq 1 rbrace.$

Since A is invertible we’ve

$x = A^{-1} y tag{1}$

in order that

$mathcal{E} = lbrace y in mathbb{R}^n: y^prime A^{-top}A^{-1} y leq 1 rbrace.$

Again to our numerical instance, computing $A^{-top}A^{-1}$ we get $B = frac{1}{2}[[5, -3];[-3, 5]]$, in order that $x^prime A^{-top}A^{-1} x = frac{5}{2}(x^2+y^2) – 3xy$ and that is what the ellipsoid appears to be like like:

identical to we designed it; squished on the prime, then rotated 45 levels counter-clockwise.

It’s common within the literature to see $n$-dimensional ellipsoids parametrized with a symmetric positive-semidefinite (I’ll clarify in a sec) matrix $Bin mathbb{R}^{ntimes n}$ through

$mathcal{E} = lbrace x in mathbb{R}^n: x^prime B x leq 1 rbrace.$

So, if we ever encounter a parametrization of this sort we all know that if we are able to factorize $B$ as

$B = A^{-top} A^{-1}, tag{2}$

then $A$ tells us how a unit ball is being remodeled to create the ellipsoid. Intuitively, a matrix $B$ is positive-semidefinite (PSD) if there exists a decomposition of the shape $B = A^{-top} A^{-1}$ the place A squishes and/or rotates however doesn’t collapse dimensions. Now, what if we don’t need our ellipsoids to be centered at $0$, what if we would like them centered at $bin mathbb{R}^n$? All we’ve to do is:

$mathcal{E} = lbrace x in mathbb{R}^n: (x-b)^prime B (x-b) leq 1 rbrace tag{3}.$

To see why that is true suppose that if earlier than the interpretation of the ellipsoid you had some extent inside it: $bar{x}$ (and thus it happy $bar{x}^prime B bar{x} leq 1$), after translation it’s important to plug in $bar{x} + b$ to get $(bar{x} + b – b)^prime B (bar{x} + b – b) = bar{x}^prime B bar{x} leq 1$.

One other approach to parametrize an ellipsoid is through a PSD matrix $C in mathbb{R}^{ntimes n}$ and a vector $c in mathbb{R}^n$. The parametrization is all $xin mathbb{R}^n$ such that:

$Vert C x + cVert_2^2 leq 1.$

How does this parametrization relate to the one in (3)? Lets broaden:

start{align}
Vert C x + cVert_2^2 & = (C x + c)^prime (C x + c) cr
& = x^prime C^prime C x + 2 x^prime C^prime c + c^prime c.
finish{align}

Increasing (3) we get

start{align}
(x-b)^prime B (x-b) = x^prime B x – 2x^prime B b + b^prime b,
finish{align}

it should observe that if we’re referring to identical elipsoid with two completely different representations the next should maintain:
$B = C^prime C$, and $C c = b$. Extra importantly, due to (2) it should maintain that

start{align}
C = A^{-1} tag{4}.
finish{align}

Why equation (4) is necessary shall be defined in a minute.

Recall the issue we try to unravel. Now we have been given a set of $N$ factors $x_1, x_2, …, x_N$ in $mathbb{R}^n$ and we wish to discover the ellipsoid of smallest quantity that accommodates it. Utilizing our second parametrization of ellipsoids, we all know that we’re in search of $C$ within the set of all PSD matrices and $c in mathbb{R}^n$ such that:

$Vert C x_n + cVert_2^2 leq 1 qquad forall n in [N].$

However how do specific that we would like the ellipsoid of smallest quantity? The trick is to recollect from linear algebra that the determinant of a matrix is proportional to how the linear transformation will increase/decreases quantity. Keep in mind how two sections in the past we had been excited about creating ellipsoids by squishing and rotating unit balls by making use of the mapping $A$? We wish to reduce $det(A^{-1})$, however how are $C$ and $A$ associated? Properly, we established this relation in equation (4). So our downside formulation is:

start{align}
min_{C, c} quad & det(C^{-1}) cr
& Vert C x_n + cVert_2^2 leq 1 qquad forall n in [N].
finish{align}

Now we have a formulation for the MVEE optimization downside, however is that this downside convex? Do there exist algorithms to effectively clear up this downside? The reply to the primary query isn’t any, it’s because $det(cdot)$ is neither convex nor concave over the set of PSD matrices (see F_G’s answer). However we’re in luck, as a result of $log(det(cdot))$ is concave. So. if we modify our goal operate to be $log(det(C^{-1})) = log(frac{1}{det(C)}) = – log(det(C))$, we’re minimizing a convex operate! To conclude that the entire optimization downside is a convex one we must present two extra issues, that the set of PSD matrices is convex, and that every of the units $lbrace C : Vert C x_n + cVert_2^2 leq 1 rbrace$ is convex. Seems each statements are true, sadly I received’t show them proper now as a result of I wish to give attention to attempting to construct sturdy portfolios. However if you wish to discover ways to show this I like to recommend these lecture notes on Semidefinite Programming or Ch. 8 from (Boyd & Vandenberghe, 2004).

To summarize, the MVEE might be formulated as the next (convex) Semidefinite Program

start{align}
min_{C, c} quad & – log(det(C)) cr
& Vert C x_n + cVert_2^2 leq 1 qquad forall n in [N].
finish{align}

This formulation is helpful as a result of there exist basic function algorithms for fixing these sorts of issues. Within the subsequent submit I’ll present how given samples of asset returns (these would be the factors $lbrace x_n rbrace$) we are able to use a MVEE to seek out uncertainty units which we are able to then incorporate into our sturdy formulation of the mean-variance portfolio downside.