Fitting Gaussian vectors in normed spaces
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: Mathematics. The day in mathematics: new theorems, new proofs, and what they open.
Ada: We're looking at the paper: "Fitting Gaussian vectors in normed spaces".
Emmy: Here's the gist of the paper. Given a family of N i.i.d.
Ada: Gaussian points in a d-dimensional normed space, what is the probability that some linear transformation maps it to the unit sphere?
Emmy: The paper initiates a study of this fitting problem in a general normed space, both asymptotically and in a fixed dimension, focusing on showing that cd2/ log d points can be fitted with high probability in the space l d infinity The geometry of the normed space is reflected in the fitting problem by showing that in dimension 2, the spaces l 2 squared and l 2 infinity are characterized by having extremal fittability properties The Normed Space Fitting Problem The paper defines Z-fittable as a cloud X1,..., XN of points in Z being mapped to the unit sphere by a linear map T: Z → Z The probability p(N, Z) is investigated, and it is noted that if N ⩽ d then the points are almost surely linearly independent and p(N, Z) = 1 The study establishes that for any normed space Z, the function N 7→ p(N, Z) is nonincreasing Dimension Obstructions The paper proves that in any d-dimensional space, one cannot fit more than d squared Gaussian points For general normed spaces, Theorem 2 states that if N > d squared then p(N, Z) = 0 This is shown by decomposing the set of Z-fittable clouds into compact sets and showing their Lebesgue measure vanishes when N > d squared Asymptotic Thresholds The paper investigates phase transitions in general normed spaces, conjecturing that the transition happens around a quadratic number of points For the space l d infinity, Theorem 3 shows there is a constant c > 0 such that if N ⩽ cd2/ log d, then lim d→∞ p(N, l d infinity) = 1 The threshold for convex position occurs on the exponential scale, with estimates provided in Theorem 5 Extremal Properties in Dimension Two A complete study in dimension 2 shows that the only non-trivial parameter is p(4, Z), which satisfies inequalities 0 ⩽ p(4, Z) ⩽ pconv(4, 2) Theorem 4 characterizes the spaces: the space Z is isometric to l 2 squared if and only if p(4, Z) = 0 The space Z is isometric to l 2 infinity if and only if p(4, Z) = pconv(4, 2) Parallelotope Fitting The parallelotope fitting problem in the space l d infinity corresponds to fitting a cloud to the boundary of a parallelotope Theorem 3 proves that there is a constant c > 0 such that if N ⩽ cd2/ log d, then lim d→∞ p(N, l d infinity) = 1 The result relies on neighborliness properties of random polytopes Deterministic Results The paper addresses questions about the maximum number of points for which p(N, Z) > 0 and p(N, Z) = pconv(N, d) in the case Z = l d infinity Proposition 4.4 shows that p(d squared, l d infinity) > 0 Proposition 4.5 states that for integers N ⩾ d, we have p(N, l d infinity) = pconv(N, d) if and only if N ⩽ 2d Symmetric Convex Position in High Dimensions The paper investigates the asymptotic behavior of pconv(N, d), showing that a sharp transition occurs at an exponential threshold Theorem 5 provides estimates for this transition, suggesting the threshold is between (√4/2)d and (√e)d points Fitting in Two-Dimensional Spaces In dimension 2, the set ∆ is defined by specific inequalities involving a − b and a + b < 1 < o < Lemma 5.3 shows that for non-Euclidean spaces, the set Lx1,x2,x3 has nonzero Lebesgue measure Theorem 4 concludes that p(4, Z) = 0 if Z is Euclidean and p(4, Z) > 0 if Z is non-Euclidean Symmetric Convex Position in High Dimensions The paper proves that for every c ∈ (0, 1), if N ⩽ c · 2d/4, then pconv(N, d) ⩾ 1 − c squared The second part of Theorem 5 shows that if N ≥ e(1/2+ε)d, then lim d→∞ pconv(N, d) = 0 This implies the threshold for convex position is exponential in size The Convex Position Obstruction Proposition 2.4 establishes the equivalence between p(N, Z) = pconv(N, d) and every cloud of N points in symmetric convex position being Z-fittable The proof uses a sequence of clouds in symmetric strictly convex position to show that almost every element is Z-fittable The Convex Position Obstruction Theorem 1 states that for d + 1 points, the cloud X is Z-fittable if and only if it is in symmetric convex position, meaning p(d + 1, Z) = pconv(d + 1, d) Proposition 2.7 shows that for N ⩾ d+2 in a strictly convex space Z, p(N, Z) d squared then p(N, Z) = 0 This is proven using covering numbers and box dimension arguments to show that the Lebesgue measure of the set of Z-fittable clouds vanishes when N > d squared The Dimension Obstruction Lemma 3.1 provides a technical bound for the dimension of Fitr,k, showing dim(Fitr,k) ≤ r(2d − r) + N(d − 1) Under the assumption that N > d squared, this implies that λNd(Fitr,k) = 0 and thus p(N, Z) = 0 The Parallelotope Fitting Problem Proposition 4.1 states that if X is l d infinity-fittable, then KN can be covered by d pairs of facets Proposition 4.5 shows that p(N, l d infinity) = pconv(N, d) if and only if N ≤ 2d The Parallelotope Fitting Problem Theorem 3 proves that there is a constant c > 0 such that if N ≤ cd2/ log d, then lim d→∞ p(N, l d infinity) = 1 This relies on the result that points are in symmetric strictly convex position and the polytope KN is k-symmetric neighborly The Parallelotope Fitting Problem Proposition 4.1 also states that if X is in symmetric strictly convex position and KN can be covered by d pairs of facets, then X is l d infinity-fittable This links the geometric properties of the polytope to the fitting property The Parallelotope Fitting Problem Proposition 4.5 shows that p(2d, l d infinity) = pconv(2d, d), and this implies p(N, l d infinity) = pconv(N, d) for every d ⩽ N ≤ 2d The proof involves showing that every centrally symmetric d-polytope with 2d antipodal pairs of vertices can be covered by d pairs of facets The Parallelotope Fitting Problem Proposition 4.4 shows that p(d squared, l d infinity) > 0 This is shown by constructing a symmetric simplicial polytope in R d with d squared pairs of vertices that can be covered by d pairs of facets The Parallelotope Fitting Problem Proposition 4.5 establishes the condition for p(N, l d infinity) = pconv(N, d) as N ≤ 2d This is proven by analyzing the combinatorial properties of centrally symmetric polytopes and their facet coverings Fitting in Two-Dimensional Spaces Theorem 4 states that the space Z is isometric to l 2 squared if and only if p(4, Z) = 0 The space Z is isometric to l 2 infinity if and only if p(4, Z) = pconv(4, 2) This result is derived from the analysis of the parameter p(4, Z), which is minimized for Euclidean spaces and maximized for spaces isometric to l 2 infinity Symmetric Convex Position in High Dimensions Theorem 5 provides estimates that suggest a sharp transition occurs at an exponential threshold The expected limit theta(p) exists and does not depend on p, falling between 21/4 and √e This suggests the threshold is exponential in size The Convex Position Obstruction Lemma 5.3 shows that for three points x1, x2, x3 in symmetric strictly convex position, the set Lx1,x2,x3 has nonzero Lebesgue measure This contrasts with the Euclidean case where the set is a unique ellipse with zero Lebesgue measure The Convex Position Obstruction Lemma 5.1 shows that for s ∈ ∆, there exists a continuous function f s from SZ to SZ such that every element in As is invertible This leads to the conclusion that for every ω ∈ omega, the vectors (e1, e2, s, ω) are Z-fittable The Convex Position Obstruction Theorem 4 states that for a non-Euclidean normed space Z of dimension 2, p(4, Z) > 0 The proof involves constructing a polytope P that cannot be covered by d pairs of facets The result is shown by considering the set of vertices and showing it cannot be covered by d pairs of facets The Convex Position Obstruction Remark 5.4 suggests that Theorem 4 might not extend to higher dimensions, noting that no 3-dimensional normed space Z satisfies p(7, Z) = pconv(7, 3) Symmetric Convex Position in High Dimensions Theorem 5 provides estimates for qconv(N, d), showing that if N ≤ c · 2d/4, then qconv(N, d) ≤ c squared and thus pconv(N, d) ⩾ 1 − c squared The second part of Theorem 5 shows that if N ≥ e(1/2+ε)d, then lim d→∞ pconv(N, d) = 0 This confirms the exponential threshold for symmetric convex position The Convex Position Obstruction Lemma 6.1 and Lemma 6.2 are used to prove the estimates in Theorem 5, showing that qconv(N, d) ≤ c squared when N is small The second inequality in (6.2) is essentially sharp The Convex Position Obstruction The proof of the second part of Theorem 5 uses concentration inequalities to show that P(E) tends to 0 uniformly over integers N ≥ exp(1/2+ε)d This confirms the exponential threshold for symmetric convex position The Dimension Obstruction Proposition 3.3 shows that p(N, l d 2) = 0 if and only if N > d(d+1)/2 This is shown by analyzing the function f(X1,..., XNd) = det(X1XT 1,..., XNdXT Nd) The result is shown by showing that the set A(X) is positive definite and open, hence of nonzero Gaussian measure The Dimension Obstruction Lemma 3.2 provides a technical bound for the dimension of Fitr,k, which implies that λNd(Fitr,k) = 0 and therefore p(N, Z) = 0 This is shown by relating covering numbers to the dimension of the set of matrices Ar k The Parallelotope Fitting Problem Proposition 4.1 shows that if X is l d infinity-fittable, then KN can be covered by d pairs of facets This is shown by showing that each linear form takes values ⩽ 1 on the polytope KN The Parallelotope Fitting Problem Proposition 4.5 shows that p(N, l d infinity) = pconv(N, d) if and only if N ≤ 2d This is proven by analyzing the combinatorial properties of centrally symmetric polytopes and their facet coverings The Fitting in Two-Dimensional Spaces Theorem 4 characterizes the spaces Z: Z is isometric to l 2 squared if and only if p(4, Z) = 0 The space Z is isometric to l 2 infinity if and only if p(4, Z) = pconv(4, 2) This result is derived from the analysis of the parameter p(4, Z), which is minimized for Euclidean spaces and maximized for spaces isometric to l 2 infinity The Convex Position Obstruction Lemma 6.3 shows that for three points x1, x2, x3 in symmetric strictly convex position, the set Lx1,x2,x3 has nonzero Lebesgue measure This contrasts with the Euclidean case where the set is a unique ellipse with zero Lebesgue measure The Parallelotope Fitting Problem Proposition 4.
Paper summary: Ada: So we've established that the paper "Fitting Gaussian vectors in normed spaces" investigates this fitting problem in a general setting, looking at both fixed dimensions and as the dimension goes to infinity. They focus specifically on showing that for the space d infinity, there are about cd squared over log d points you can fit with high probability.
Emmy: And they use the geometry of the normed space itself to characterize how well these spaces fit Gaussian clouds. They show that in dimension two, for example, the spaces two squared and two infinity are special because they have extremal fittability properties compared to other spaces <ref:2610.20299#pg3>.
Kolya: What's interesting is that they connect this fitting problem to the parallelotope fitting problem in d infinity, which relates fitting points to covering a polytope with d pairs of facets. They use known neighborliness properties of random polytopes for that part.
Ada: And they also have some deterministic results. For the space d infinity, they show that if you have exactly 2d points, the probability is equal to a value related to convex position in dimension d, and this holds for all N between those two values <ref:2610.20299#pg1>.
Emmy: It really boils down to how the shape of the space dictates whether you can fit those random Gaussian points onto its boundary under a linear map. The structure of the norm matters, not just the dimension.
Conclusion: Ada: Looking at "Fitting Gaussian vectors in normed spaces," we see they tackle this fitting problem across different mathematical landscapes, from fixed dimensions to the infinite-dimensional limit. They aren't just looking for a simple answer; they are characterizing when these fits are possible based on the underlying geometry of the space Z.
Emmy: The core implication is that in general normed spaces, there's a clear threshold on the number of points you can handle before fitting becomes impossible. This threshold scales with d squared, but for specific spaces like d infinity, it's more delicately balanced around d squared divided by log d.
Kolya: What this means for us is that if you're dealing with data in a high-dimensional setting where the geometry isn't just standard Euclidean space, you have to be very careful about how many samples you collect before your fitting strategy breaks down. The results on symmetric convex position also point toward an exponential threshold for when those fits become likely in high dimensions.
Ada: So, they've given us concrete limits and phase transitions across various norms, showing that the geometry of the space is deeply intertwined with the probability of fitting random points onto its boundary. That's what this paper is about.
University of Lyon 1 · INSA Lyon · CNRS
math.PR, math.FA
Submitted: 2026-10-14
Updated: 2026-11-10
Comments: V2: Improvement on Theorem 5(sharp version)
Project page: https://emmanouilstavrakakis.github.io
License: http://creativecommons.org/licenses/by/4.0/
Importance score: 64/100
The gist: Given a family of N i.i.d.
Key concepts
- Z-fittable
- A set of points X in a space Z is Z-fittable if there exists a linear map T from Z to itself that maps every point in the set X onto the unit sphere. This concept measures how well the points can be 'fitted' by a linear transformation within that specific normed space.
- Dimension Obstruction
- This concept establishes a hard limit on the number of points that can be fitted in any d-dimensional space. The paper proves that for any normed space, if N is greater than $d^2$, the probability of fitting the points becomes zero, meaning $N > d^2$ is impossible.
- Convex Position Obstruction
- This relates the fitting problem to geometric arrangements of points. A set of points is in symmetric convex position if it satisfies specific geometric constraints. The paper shows that a cloud X is Z-fittable if and only if it belongs to this specific symmetric convex position.
- Asymptotic Thresholds
- This refers to the critical number of points N needed for the fitting probability to transition from near zero to near one as the dimension d grows. The paper suggests that for spaces like $l_d$ infinity, this threshold is around $c d^2 / ext{log } d$, indicating a quadratic dependence on dimension.
Terminology
Summary
Given a family of N i. p. 0 FITTING GAUSSIAN CLOUDS IN NORMED SPACES
GUILLAUME AUBRUN AND EMMANOUIL STAVRAKAKIS
Abstract. Given a family of N i. Given a family of N i. Gaussian points in a d-dimensional normed space, what is the
probability that some linear transformation maps it to the unit sphere?Where the paper says it
Where the paper says it
The Normed Space Fitting Problem
The paper defines Z-fittable as a cloud X1,..., XN of points in Z being mapped to the unit sphere by a linear map T: Z → Z The probability p(N, Z) is investigated, and it is noted that if N ⩽ d then the points are almost surely linearly independent and p(N, Z) = 1 The study establishes that for any normed space Z, the function N 7→ p(N, Z) is nonincreasing
Dimension Obstructions
The paper proves that in any d-dimensional space, one cannot fit more than d squared Gaussian points For general normed spaces, Theorem 2 states that if N > d squared then p(N, Z) = 0 This is shown by decomposing the set of Z-fittable clouds into compact sets and showing their Lebesgue measure vanishes when N > d squared
Asymptotic Thresholds
The paper investigates phase transitions in general normed spaces, conjecturing that the transition happens around a quadratic number of points For the space l d infinity, Theorem 3 shows there is a constant c > 0 such that if N ⩽ cd2/ log d, then lim d→∞ p(N, l d infinity) = 1 The threshold for convex position occurs on the exponential scale, with estimates provided in Theorem 5
Extremal Properties in Dimension Two
A complete study in dimension 2 shows that the only non-trivial parameter is p(4, Z), which satisfies inequalities 0 ⩽ p(4, Z) ⩽ pconv(4, 2) Theorem 4 characterizes the spaces: the space Z is isometric to l 2 squared if and only if p(4, Z) = 0 The space Z is isometric to l 2 infinity if and only if p(4, Z) = pconv(4, 2)
Parallelotope Fitting
The parallelotope fitting problem in the space l d infinity corresponds to fitting a cloud to the boundary of a parallelotope Theorem 3 proves that there is a constant c > 0 such that if N ⩽ cd2/ log d, then lim d→∞ p(N, l d infinity) = 1 The result relies on neighborliness properties of random polytopes
Deterministic Results
The paper addresses questions about the maximum number of points for which p(N, Z) > 0 and p(N, Z) = pconv(N, d) in the case Z = l d infinity Proposition 4.4 shows that p(d squared, l d infinity) > 0 Proposition 4. p. 0 We prove a partial
result in this direction by showing that p(N, ℓd
∞) ≈ 1 if N ⩽ cd2/ log d (see Theorem 3). A dimension
argument shows that, in any d-dimensional space, we cannot fit more than d
2 Gaussian points (see
Theorem 2).Where the paper says it
Symmetric Convex Position in High Dimensions
The paper investigates the asymptotic behavior of pconv(N, d), showing that a sharp transition occurs at an exponential threshold Theorem 5 provides estimates for this transition, suggesting the threshold is between (√4/2)d and (√e)d points
Fitting in Two-Dimensional Spaces
In dimension 2, the set ∆ is defined by specific inequalities involving a − b and a + b < 1 < o < Lemma 5.3 shows that for non-Euclidean spaces, the set Lx1,x2,x3 has nonzero Lebesgue measure Theorem 4 concludes that p(4, Z) = 0 if Z is Euclidean and p(4, Z) > 0 if Z is non-Euclidean
The paper proves that for every c ∈ (0, 1), if N ⩽ c · 2d/4, then pconv(N, d) ⩾ 1 − c squared The second part of Theorem 5 shows that if N ≥ e(1/2+ε)d, then lim d→∞ pconv(N, d) = 0 This implies the threshold for convex position is exponential in size
The Convex Position Obstruction
Proposition 2.4 establishes the equivalence between p(N, Z) = pconv(N, d) and every cloud of N points in symmetric convex position being Z-fittable The proof uses a sequence of clouds in symmetric strictly convex position to show that almost every element is Z-fittable
Theorem 1 states that for d + 1 points, the cloud X is Z-fittable if and only if it is in symmetric convex position, meaning p(d + 1, Z) = pconv(d + 1, d) Proposition 2.7 shows that for N ⩾ d+2 in a strictly convex space Z, p(N, Z) d squared then p(N, Z) = 0 This is proven using covering numbers and box dimension arguments to show that the Lebesgue measure of the set of Z-fittable clouds vanishes when N > d squared
The Dimension Obstruction
Lemma 3.1 provides a technical bound for the dimension of Fitr,k, showing dim(Fitr,k) ≤ r(2d − r) + N(d − 1) Under the assumption that N > d squared, this implies that λNd(Fitr,k) = 0 and thus p(N, Z) = 0
The Parallelotope Fitting Problem
Proposition 4.1 states that if X is l d infinity-fittable, then KN can be covered by d pairs of facets Proposition 4. p. 9 , XN ) be a cloud in R
d and KN = absconv{X1, . If X is ℓ
d
∞-fittable, then KN can be covered by d pairs of facets.Where the paper says it
Theorem 3 proves that there is a constant c > 0 such that if N ≤ cd2/ log d, then lim d→∞ p(N, l d infinity) = 1 This relies on the result that points are in symmetric strictly convex position and the polytope KN is k-symmetric neighborly
Proposition 4.1 also states that if X is in symmetric strictly convex position and KN can be covered by d pairs of facets, then X is l d infinity-fittable This links the geometric properties of the polytope to the fitting property
Proposition 4.5 shows that p(2d, l d infinity) = pconv(2d, d), and this implies p(N, l d infinity) = pconv(N, d) for every d ⩽ N ≤ 2d The proof involves showing that every centrally symmetric d-polytope with 2d antipodal pairs of vertices can be covered by d pairs of facets
Proposition 4.4 shows that p(d squared, l d infinity) > 0 This is shown by constructing a symmetric simplicial polytope in R d with d squared pairs of vertices that can be covered by d pairs of facets
Proposition 4.5 establishes the condition for p(N, l d infinity) = pconv(N, d) as N ≤ 2d This is proven by analyzing the combinatorial properties of centrally symmetric polytopes and their facet coverings
Theorem 4 states that the space Z is isometric to l 2 squared if and only if p(4, Z) = 0 The space Z is isometric to l 2 infinity if and only if p(4, Z) = pconv(4, 2) This result is derived from the analysis of the parameter p(4, Z), which is minimized for Euclidean spaces and maximized for spaces isometric to l 2 infinity
Theorem 5 provides estimates that suggest a sharp transition occurs at an exponential threshold The expected limit theta(p) exists and does not depend on p, falling between 21/4 and √e This suggests the threshold is exponential in size
Lemma 5.3 shows that for three points x1, x2, x3 in symmetric strictly convex position, the set Lx1,x2,x3 has nonzero Lebesgue measure This contrasts with the Euclidean case where the set is a unique ellipse with zero Lebesgue measure
Lemma 5.1 shows that for s ∈ ∆, there exists a continuous function f s from SZ to SZ such that every element in As is invertible This leads to the conclusion that for every ω ∈ omega, the vectors (e1, e2, s, ω) are Z-fittable
Theorem 4 states that for a non-Euclidean normed space Z of dimension 2, p(4, Z) > 0 The proof involves constructing a polytope P that cannot be covered by d pairs of facets The result is shown by considering the set of vertices and showing it cannot be covered by d pairs of facets
Remark 5.4 suggests that Theorem 4 might not extend to higher dimensions, noting that no 3-dimensional normed space Z satisfies p(7, Z) = pconv(7, 3)
Theorem 5 provides estimates for qconv(N, d), showing that if N ≤ c · 2d/4, then qconv(N, d) ≤ c squared and thus pconv(N, d) ⩾ 1 − c squared The second part of Theorem 5 shows that if N ≥ e(1/2+ε)d, then lim d→∞ pconv(N, d) = 0 This confirms the exponential threshold for symmetric convex position
Lemma 6.1 and Lemma 6. p. 2 Fitting d + 1 points in a d-dimensional normed space. We will need the following lemma to
describe precisely the interior of the absulute convex hull of linearly independent vectors. For any normed
space Z, the function N 7→ p(N, Z) is obviously nonincreasing and one might conjecture that, as for
Euclidean spaces, the phase transition happens around a quadratic number of points. We prove a partial
result in this direction by showing that p(N, ℓd
∞) ≈ 1 if N ⩽ cd2/ log d (see Theorem 3).Where the paper says it
Where the paper says it
The proof of the second part of Theorem 5 uses concentration inequalities to show that P(E) tends to 0 uniformly over integers N ≥ exp(1/2+ε)d This confirms the exponential threshold for symmetric convex position
Proposition 3.3 shows that p(N, l d 2) = 0 if and only if N > d(d+1)/2 This is shown by analyzing the function f(X1,. p. 9 This subsection is dedicated to proving Theorem 3. We will deduce Theorem 3 from the following statement which appears in the theory of compressed
sensing, where neighborliness of random polytopes has been shown to be connected to the ability of
random matrices to reconstruct sparse vectors by the ℓ1-minimization procedure. Consider the function f : (R
d
)
Nd → R defined by
f(X1, . , XNd
) = det(X1XT
1
, .Where the paper says it
Where the paper says it
Lemma 3.2 provides a technical bound for the dimension of Fitr,k, which implies that λNd(Fitr,k) = 0 and therefore p(N, Z) = 0 This is shown by relating covering numbers to the dimension of the set of matrices Ar k
Proposition 4.1 shows that if X is l d infinity-fittable, then KN can be covered by d pairs of facets This is shown by showing that each linear form takes values ⩽ 1 on the polytope KN
Proposition 4.5 shows that p(N, l d infinity) = pconv(N, d) if and only if N ≤ 2d This is proven by analyzing the combinatorial properties of centrally symmetric polytopes and their facet coverings
The Fitting in Two-Dimensional Spaces
Theorem 4 characterizes the spaces Z: Z is isometric to l 2 squared if and only if p(4, Z) = 0 The space Z is isometric to l 2 infinity if and only if p(4, Z) = pconv(4, 2) This result is derived from the analysis of the parameter p(4, Z), which is minimized for Euclidean spaces and maximized for spaces isometric to l 2 infinity
Lemma 6.3 shows that for three points x1, x2, x3 in symmetric strictly convex position, the set Lx1,x2,x3 has nonzero Lebesgue measure This contrasts with the Euclidean case where the set is a unique ellipse with zero Lebesgue measure
Proposition 4.
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Develop an AI system capable of determining if a given set of Gaussian points in a general normed space Z is Z-fittable by checking if they are in symmetric convex position, based on Theorem 1:
The cloud X is Z-fittable if and only if it is in symmetric convex position.
-
Implement an AI that can predict the asymptotic behavior of the probability p(N, Z) for a general normed space Z as N approaches infinity by utilizing the phase transition results described in Section 1.
-
Create an AI that can classify a given 2-dimensional normed space Z as isometric to Euclidean space or to the space l2 infinity based on the value of p(4, Z), using Theorem 4:
The space Z is isometric to l22 if and only if p(4, Z) = 0
andThe space Z is isometric to l2inf if and only if p(4, Z) = pconv(4, 2).
-
Design an AI that can estimate the threshold for symmetric convex position in high dimensions by leveraging the concentration inequalities provided in Theorem 5:
For every c ∈ (0, 1), if N ⩽ c · 2d/4, then pconv(N, d) ⩾ 1 − c squared.
-
Build an AI that can analyze a cloud of points to decide if it is l d infinity-fittable by checking combinatorial properties of its absolute convex hull using Section 4:
If X is l d infinity-fittable, then KN can be covered by d pairs of facets.
Abstract
Given a family of N i.i.d. Gaussian points in a d-dimensional normed space, what is the probability that some linear transformation maps it to the unit sphere? The case of a Euclidean space is known as the ellipsoid fitting problem and has recently attracted major attention. We initiate a study of this fitting problem in a general normed space, both asymptotically and in a fixed dimension. We specifically focus on the space infinity d, where a combinatorial reformulation allows us to show that cd 2/ d points can be fitted with high probability. We illustrate that the geometry of the normed space is reflected in the fitting problem by showing that in dimension 2, the spaces 2 squared and infinity squared are characterized by having extremal fittability properties. We also study the probability that a family of N i.i.d. Gaussian points in R d is in convex position and show that a sharp threshold occurs around the value N= (d/2e).
Sources
- Sharp Phase Transition for Ellipsoid Fitting
- A Nearly Tight Bound for Fitting an Ellipsoid to Gaussian Random Points
- Universality and sharp thresholds for ellipsoid fitting
- The sharp SAT/UNSAT phase transition in random ellipsoid fitting
Related papers
- Rank-One HCIZ Integrals and Multiplicative Convolutions
- Markov Chain CLTs: Resolving Open Problems
- Marked stable L'evy processes in Brownian local time
- A Sharp Refinement of Samuels' Inequality via Cap Moves
- A zero-one law for swap-invariant events in uniform spanning forests
- Bernoulli flow for Erd s-R'enyi graphs