More Like this

1. Differentiability of the argmin function and a minimum principle for semiconcave subsolutions

   Ross, Julius; Witt Nystrom, David (January 2020, Journal of convex analysis)

   Suppose $$f(x,y) + \frac{\kappa}{2} \|x\|^2 - \frac{\sigma}{2}\|y\|^2$$ is convex where $$\kappa\ge 0, \sigma>0$$, and the argmin function $$\gamma(x) = \{ \gamma : \inf_y f(x,y) = f(x,\gamma)\}$$ exists and is single valued. We will prove $$\gamma$$ is differentiable almost everywhere. As an application we deduce a minimum principle for certain semiconcave subsolutions. 

   more » « less
2. Tight Bounds for ℓ ₁ Oblivious Subspace Embeddings

   https://doi.org/10.1145/3477537  

   Wang, Ruosong; Woodruff, David P. (January 2022, ACM Transactions on Algorithms)

   An \ell _p oblivious subspace embedding is a distribution over r \times n matrices \Pi such that for any fixed n \times d matrix A , \[ \Pr _{\Pi }[\textrm {for all }x, \ \Vert Ax\Vert _p \le \Vert \Pi Ax\Vert _p \le \kappa \Vert Ax\Vert _p] \ge 9/10,\] where r is the dimension of the embedding, \kappa is the distortion of the embedding, and for an n -dimensional vector y , \Vert y\Vert _p = (\sum _{i=1}^n |y_i|^p)^{1/p} is the \ell _p -norm. Another important property is the sparsity of \Pi , that is, the maximum number of non-zero entries per column, as this determines the running time of computing \Pi A . While for p = 2 there are nearly optimal tradeoffs in terms of the dimension, distortion, and sparsity, for the important case of 1 \le p \lt 2 , much less was known. In this article, we obtain nearly optimal tradeoffs for \ell _1 oblivious subspace embeddings, as well as new tradeoffs for 1 \lt p \lt 2 . Our main results are as follows: (1) We show for every 1 \le p \lt 2 , any oblivious subspace embedding with dimension r has distortion \[ \kappa = \Omega \left(\frac{1}{\left(\frac{1}{d}\right)^{1 / p} \log ^{2 / p}r + \left(\frac{r}{n}\right)^{1 / p - 1 / 2}}\right).\] When r = {\operatorname{poly}}(d) \ll n in applications, this gives a \kappa = \Omega (d^{1/p}\log ^{-2/p} d) lower bound, and shows the oblivious subspace embedding of Sohler and Woodruff (STOC, 2011) for p = 1 is optimal up to {\operatorname{poly}}(\log (d)) factors. (2) We give sparse oblivious subspace embeddings for every 1 \le p \lt 2 . Importantly, for p = 1 , we achieve r = O(d \log d) , \kappa = O(d \log d) and s = O(\log d) non-zero entries per column. The best previous construction with s \le {\operatorname{poly}}(\log d) is due to Woodruff and Zhang (COLT, 2013), giving \kappa = \Omega (d^2 {\operatorname{poly}}(\log d)) or \kappa = \Omega (d^{3/2} \sqrt {\log n} \cdot {\operatorname{poly}}(\log d)) and r \ge d \cdot {\operatorname{poly}}(\log d) ; in contrast our r = O(d \log d) and \kappa = O(d \log d) are optimal up to {\operatorname{poly}}(\log (d)) factors even for dense matrices. We also give (1) \ell _p oblivious subspace embeddings with an expected 1+\varepsilon number of non-zero entries per column for arbitrarily small \varepsilon \gt 0 , and (2) the first oblivious subspace embeddings for 1 \le p \lt 2 with O(1) -distortion and dimension independent of n . Oblivious subspace embeddings are crucial for distributed and streaming environments, as well as entrywise \ell _p low-rank approximation. Our results give improved algorithms for these applications. 

   more » « less
3. A single-point Reshetnyak’s theorem

   https://doi.org/10.1090/tran/9415  

   Kangasniemi, Ilmari; Onninen, Jani (May 2025, Transactions of the American Mathematical Society)

   We prove a single-value version of Reshetnyak’s theorem. Namely, if a non-constant map $f\in W_{\mathrm{l}\mathrm{o}\mathrm{c}}^{1,n}(\mathrm{\Omega },{\mathbb{R}}^n)$ from a domain $\mathrm{\Omega }\subset {\mathbb{R}}^n$ satisfies the estimate $\left|Df\right(x){|}^n\le K{J}_f(x)+\mathrm{\Sigma }(x\left)\right|f\left(x\right)-y_0{|}^n$ at almost every $x\in \mathrm{\Omega }$ for some $K\ge 1$, $y_0\in {\mathbb{R}}^n$ and $\mathrm{\Sigma }\in L_{\mathrm{l}\mathrm{o}\mathrm{c}}^{1+\epsilon }\left(\mathrm{\Omega }\right)$, then $f^{-1}\left\{y_0\right\}$ is discrete, the local index $i(x,f)$ is positive in $f^{-1}\left\{y_0\right\}$, and every neighborhood of a point of $f^{-1}\left\{y_0\right\}$ is mapped to a neighborhood of $y_0$. Assuming this estimate for a fixed $K$ at every $y_0\in {\mathbb{R}}^n$ is equivalent to assuming that the map $f$ is $K$-quasiregular, even if the choice of $\mathrm{\Sigma }$ is different for each $y_0$. Since the estimate also yields a single-value Liouville theorem, it hence appears to be a good pointwise definition of $K$-quasiregularity. As a corollary of our single-value Reshetnyak’s theorem, we obtain a higher-dimensional version of the argument principle that played a key part in the solution to the Calderón problem. 

   more » « less
4. On finite energy monopoles on $$C x \Sigma$$.

   Wang, Donghao (July 2019, ArXiv.org)

   Let $$X=\mathbb{C}\times\Sigma$$ be the product of the complex plane and a compact Riemann surface. We establish a classification theorem of solutions to the Seiberg-Witten equation on $$X$$ with finite analytic energy. The spin bundle $$S^+\to X$$ splits as $$L^+\oplus L^-$$. When $$2-2g\leq c_1(S^+)[\Sigma]<0$$, the moduli space is in bijection with the moduli space of pairs $$((L^+,\bar{\partial}), f)$$ where $$(L^+,\bar{\partial})$$ is a holomorphic structure on $L^+$ and $$f: \mathbb{C}\to H^0(\Sigma, L^+,\bar{\partial})$$ is a polynomial map. Moreover, the solution has analytic energy $$-4\pi^2d\cdot c_1(S^+)[\Sigma]$$ if $$f$$ has degree $$d$$. When $$c_1(S^+)=0$$, all solutions are reducible and the moduli space is the space of flat connections on $$\bigwedge^2 S^+$$. We also estimate the decay rate at infinity for these solutions. 

   more » « less
5. Zeroes of polynomials on definable hypersurfaces: pathologies exist, but they are rare

   https://doi.org/10.1093/qmath/haz022  

   Basu, Saugata; Lerario, Antonio; Natarajan, Abhiram (October 2019, The Quarterly Journal of Mathematics)

   Abstract Given a sequence $$\{Z_d\}_{d\in \mathbb{N}}$$ of smooth and compact hypersurfaces in $${\mathbb{R}}^{n-1}$$, we prove that (up to extracting subsequences) there exists a regular definable hypersurface $$\Gamma \subset {\mathbb{R}}\textrm{P}^n$$ such that each manifold $$Z_d$$ is diffeomorphic to a component of the zero set on $$\Gamma$$ of some polynomial of degree $$d$$. (This is in sharp contrast with the case when $$\Gamma$$ is semialgebraic, where for example the homological complexity of the zero set of a polynomial $$p$$ on $$\Gamma$$ is bounded by a polynomial in $$\deg (p)$$.) More precisely, given the above sequence of hypersurfaces, we construct a regular, compact, semianalytic hypersurface $$\Gamma \subset {\mathbb{R}}\textrm{P}^{n}$$ containing a subset $$D$$ homeomorphic to a disk, and a family of polynomials $$\{p_m\}_{m\in \mathbb{N}}$$ of degree $$\deg (p_m)=d_m$$ such that $$(D, Z(p_m)\cap D)\sim ({\mathbb{R}}^{n-1}, Z_{d_m}),$$ i.e. the zero set of $$p_m$$ in $$D$$ is isotopic to $$Z_{d_m}$$ in $${\mathbb{R}}^{n-1}$$. This says that, up to extracting subsequences, the intersection of $$\Gamma$$ with a hypersurface of degree $$d$$ can be as complicated as we want. We call these ‘pathological examples’. In particular, we show that for every $$0 \leq k \leq n-2$$ and every sequence of natural numbers $$a=\{a_d\}_{d\in \mathbb{N}}$$ there is a regular, compact semianalytic hypersurface $$\Gamma \subset {\mathbb{R}}\textrm{P}^n$$, a subsequence $$\{a_{d_m}\}_{m\in \mathbb{N}}$$ and homogeneous polynomials $$\{p_{m}\}_{m\in \mathbb{N}}$$ of degree $$\deg (p_m)=d_m$$ such that (0.1)$$\begin{equation}b_k(\Gamma\cap Z(p_m))\geq a_{d_m}.\end{equation}$$ (Here $$b_k$$ denotes the $$k$$th Betti number.) This generalizes a result of Gwoździewicz et al. [13]. On the other hand, for a given definable $$\Gamma$$ we show that the Fubini–Study measure, in the Gaussian probability space of polynomials of degree $$d$$, of the set $$\Sigma _{d_m,a, \Gamma }$$ of polynomials verifying (0.1) is positive, but there exists a constant $$c_\Gamma$$ such that $$\begin{equation*}0<{\mathbb{P}}(\Sigma_{d_m, a, \Gamma})\leq \frac{c_{\Gamma} d_m^{\frac{n-1}{2}}}{a_{d_m}}.\end{equation*}$$ This shows that the set of ‘pathological examples’ has ‘small’ measure (the faster $$a$$ grows, the smaller the measure and pathologies are therefore rare). In fact we show that given $$\Gamma$$, for most polynomials a Bézout-type bound holds for the intersection $$\Gamma \cap Z(p)$$: for every $$0\leq k\leq n-2$$ and $t>0$: $$\begin{equation*}{\mathbb{P}}\left(\{b_k(\Gamma\cap Z(p))\geq t d^{n-1} \}\right)\leq \frac{c_\Gamma}{td^{\frac{n-1}{2}}}.\end{equation*}$$ 

   more » « less