Random sections of ellipsoids and the power of random information

Abstract

We study the circumradius of the intersection of an <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="m"> <mml:semantics> <mml:mi>m</mml:mi> <mml:annotation encoding="application/x-tex">m</mml:annotation> </mml:semantics> </mml:math> </inline-formula> -dimensional ellipsoid <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="script upper E"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi class="MJX-tex-caligraphic" mathvariant="script">E</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">\mathcal E</mml:annotation> </mml:semantics> </mml:math> </inline-formula> with semi-axes <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="sigma 1 greater-than-or-equal-to midline-horizontal-ellipsis greater-than-or-equal-to sigma Subscript m"> <mml:semantics> <mml:mrow> <mml:msub> <mml:mi> σ </mml:mi> <mml:mn>1</mml:mn> </mml:msub> <mml:mo> ≥ </mml:mo> <mml:mo> ⋯ </mml:mo> <mml:mo> ≥ </mml:mo> <mml:msub> <mml:mi> σ </mml:mi> <mml:mi>m</mml:mi> </mml:msub> </mml:mrow> <mml:annotation encoding="application/x-tex">\sigma _1\geq \dots \geq \sigma _m</mml:annotation> </mml:semantics> </mml:math> </inline-formula> with random subspaces of codimension <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="n"> <mml:semantics> <mml:mi>n</mml:mi> <mml:annotation encoding="application/x-tex">n</mml:annotation> </mml:semantics> </mml:math> </inline-formula> , where <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="n"> <mml:semantics> <mml:mi>n</mml:mi> <mml:annotation encoding="application/x-tex">n</mml:annotation> </mml:semantics> </mml:math> </inline-formula> can be much smaller than <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="m"> <mml:semantics> <mml:mi>m</mml:mi> <mml:annotation encoding="application/x-tex">m</mml:annotation> </mml:semantics> </mml:math> </inline-formula> . We find that, under certain assumptions on <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="sigma"> <mml:semantics> <mml:mi> σ </mml:mi> <mml:annotation encoding="application/x-tex">\sigma</mml:annotation> </mml:semantics> </mml:math> </inline-formula> , this random radius <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="script upper R Subscript n Baseline equals script upper R Subscript n Baseline left-parenthesis sigma right-parenthesis"> <mml:semantics> <mml:mrow> <mml:msub> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi class="MJX-tex-caligraphic" mathvariant="script">R</mml:mi> </mml:mrow> <mml:mi>n</mml:mi> </mml:msub> <mml:mo>=</mml:mo> <mml:msub> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi class="MJX-tex-caligraphic" mathvariant="script">R</mml:mi> </mml:mrow> <mml:mi>n</mml:mi> </mml:msub> <mml:mo stretchy="false">(</mml:mo> <mml:mi> σ </mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">\mathcal {R}_n=\mathcal {R}_n(\sigma )</mml:annotation> </mml:semantics> </mml:math> </inline-formula> is of the same order as the minimal such radius <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="sigma Subscript n plus 1"> <mml:semantics> <mml:msub> <mml:mi> σ </mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi>n</mml:mi> <mml:mo>+</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:msub> <mml:annotation encoding="application/x-tex">\sigma _{n+1}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> with high probability. In other situations <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="script upper R Subscript n"> <mml:semantics> <mml:msub> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi class="MJX-tex-caligraphic" mathvariant="script">R</mml:mi> </mml:mrow> <mml:mi>n</mml:mi> </mml:msub> <mml:annotation encoding="application/x-tex">\mathcal {R}_n</mml:annotation> </mml:semantics> </mml:math> </inline-formula> is close to the maximum <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="sigma 1"> <mml:semantics> <mml:msub> <mml:mi> σ </mml:mi> <mml:mn>1</mml:mn> </mml:msub> <mml:annotation encoding="application/x-tex">\sigma _1</mml:annotation> </mml:semantics> </mml:math> </inline-formula> . The random variable <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="script upper R Subscript n"> <mml:semantics> <mml:msub> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi class="MJX-tex-caligraphic" mathvariant="script">R</mml:mi> </mml:mrow> <mml:mi>n</mml:mi> </mml:msub> <mml:annotation encoding="application/x-tex">\mathcal {R}_n</mml:annotation> </mml:semantics> </mml:math> </inline-formula> naturally corresponds to the worst-case error of the best algorithm based on random information for <inline-formula content-type="math/mathml">

Topics & Concepts