Search for: All records

We establish a family of isoperimetric inequalities for sets that interpolate between intersection bodies and dualL_{p}-centroid bodies. This provides a bridge between the Busemann intersection inequality and the Lutwak–Zhang inequality. The approach depends on new empirical versions of these inequalities. 

Abstract This note addresses the question of optimally estimating a linear functional of an object acquired through linear observations corrupted by random noise, where optimality pertains to a worst-case setting tied to a symmetric, convex and closed model set containing the object. It complements the article ‘Statistical Estimation and Optimal Recovery’ published in the Annals of Statistics in 1994. There, Donoho showed (among other things) that, for Gaussian noise, linear maps provide near-optimal estimation schemes relatively to a performance measure relevant in Statistical Estimation. Here, we advocate for a different performance measure arguably more relevant in Optimal Recovery. We show that, relatively to this new measure, linear maps still provide near-optimal estimation schemes even if the noise is merely log-concave. Our arguments, which make a connection to the deterministic noise situation and bypass properties specific to the Gaussian case, offer an alternative to parts of Donoho’s proof. 

We consider the sensitivity of real zeros of structured polynomial systems to pertubations of their coefficients. In particular, we provide explicit estimates for condition numbers of structured random real polynomial systems and extend these estimates to the smoothed analysis setting. 

Suppose $$F:=(f_1,\ldots,f_n)$$ is a system of random $$n$$-variate polynomials with $$f_i$$ having degree $$\leq\!d_i$$ and the coefficient of $$x^{a_1}_1\cdots x^{a_n}_n$$ in $$f_i$$ being an independent complex Gaussian of mean $$0$$ and variance $$\frac{d_i!}{a_1!\cdots a_n!\left(d_i-\sum^n_{j=1}a_j \right)!}$$. Recent progress on Smale's 17$$\thth$$ Problem by Lairez --- building upon seminal work of Shub, Beltran, Pardo, B\"{u}rgisser, and Cucker --- has resulted in a deterministic algorithm that finds a single (complex) approximate root of $$F$$ using just $$N^{O(1)}$$ arithmetic operations on average, where $$N\!:=\!\sum^n_{i=1}\frac{(n+d_i)!}{n!d_i!}$$ ($$=n(n+\max_i d_i)^{O(\min\{n,\max_i d_i)\}}$$) is the maximum possible total number of monomial terms for such an $$F$$. However, can one go faster when the number of terms is smaller, and we restrict to real coefficient and real roots? And can one still maintain average-case polynomial-time with more general probability measures? We show the answer is yes when $$F$$ is instead a binomial system --- a case whose numerical solution is a key step in polyhedral homotopy algorithms for solving arbitrary polynomial systems. We give a deterministic algorithm that finds a real approximate root (or correctly decides there are none) using just $$O(n^3\log^2(n\max_i d_i))$$ arithmetic operations on average. Furthermore, our approach allows Gaussians with arbitrary variance. We also discuss briefly the obstructions to maintaining average-case time polynomial in $$n\log \max_i d_i$$ when $$F$$ has more terms. 

We consider the sensitivity of real roots of polynomial systems with respect to perturbations of the coefficients. In particular --- for a version of the condition number defined by Cucker and used later by Cucker, Krick, Malajovich, and Wschebor --- we establish new probabilistic estimates that allow a much broader family of measures than considered earlier. We also generalize further by allowing over-determined systems. In Part II, we study smoothed complexity and how sparsity (in the sense of restricting which terms can appear) can help further improve earlier condition number estimates.