More Like this

1. Fast Regression for Structured Inputs

   Meyer, Raphael; Musco, Cameron; Musco, Christopher; Woodruff, David P.; Zhou, Samson (April 2022, International Conference on Learning Representations (ICLR))

   We study the $$\ell_p$$ regression problem, which requires finding $$\mathbf{x}\in\mathbb R^{d}$$ that minimizes $$\|\mathbf{A}\mathbf{x}-\mathbf{b}\|_p$$ for a matrix $$\mathbf{A}\in\mathbb R^{n \times d}$$ and response vector $$\mathbf{b}\in\mathbb R^{n}$$. There has been recent interest in developing subsampling methods for this problem that can outperform standard techniques when $$n$$ is very large. However, all known subsampling approaches have run time that depends exponentially on $$p$$, typically, $$d^{\mathcal{O}(p)}$$, which can be prohibitively expensive. We improve on this work by showing that for a large class of common \emph{structured matrices}, such as combinations of low-rank matrices, sparse matrices, and Vandermonde matrices, there are subsampling based methods for $$\ell_p$$ regression that depend polynomially on $$p$$. For example, we give an algorithm for $$\ell_p$$ regression on Vandermonde matrices that runs in time $$\mathcal{O}(n\log^3 n+(dp^2)^{0.5+\omega}\cdot\text{polylog}\,n)$$, where $$\omega$$ is the exponent of matrix multiplication. The polynomial dependence on $$p$$ crucially allows our algorithms to extend naturally to efficient algorithms for $$\ell_\infty$$ regression, via approximation of $$\ell_\infty$$ by $$\ell_{\mathcal{O}(\log n)}$$. Of practical interest, we also develop a new subsampling algorithm for $$\ell_p$$ regression for arbitrary matrices, which is simpler than previous approaches for $$p \ge 4$$. 

   more » « less
2. COUNTABLE LENGTH EVERYWHERE CLUB UNIFORMIZATION

   https://doi.org/10.1017/jsl.2022.78  

   CHAN, WILLIAM; JACKSON, STEPHEN; TRANG, NAM (November 2022, The Journal of Symbolic Logic)

   Abstract Assume $$\mathsf {ZF} + \mathsf {AD}$$ and all sets of reals are Suslin. Let $$\Gamma $$ be a pointclass closed under $$\wedge $$ , $$\vee $$ , $$\forall ^{\mathbb {R}}$$ , continuous substitution, and has the scale property. Let $$\kappa = \delta (\Gamma )$$ be the supremum of the length of prewellorderings on $$\mathbb {R}$$ which belong to $$\Delta = \Gamma \cap \check \Gamma $$ . Let $$\mathsf {club}$$ denote the collection of club subsets of $$\kappa $$ . Then the countable length everywhere club uniformization holds for $$\kappa $$ : For every relation $$R \subseteq {}^{<{\omega _1}}\kappa \times \mathsf {club}$$ with the property that for all $$\ell \in {}^{<{\omega _1}}\kappa $$ and clubs $$C \subseteq D \subseteq \kappa $$ , $$R(\ell ,D)$$ implies $$R(\ell ,C)$$ , there is a uniformization function $$\Lambda : \mathrm {dom}(R) \rightarrow \mathsf {club}$$ with the property that for all $$\ell \in \mathrm {dom}(R)$$ , $$R(\ell ,\Lambda (\ell ))$$ . In particular, under these assumptions, for all $$n \in \omega $$ , $$\boldsymbol {\delta }^1_{2n + 1}$$ satisfies the countable length everywhere club uniformization. 

   more » « less
3. Faster Kernel Matrix Algebra via Density Estimation

   Backurs, A; Indyk, P; Musco, C; Wagner, T (January 2021, International Conference on Machine Learning)

   null (Ed.)

   We study fast algorithms for computing basic properties of an n x n positive semidefinite kernel matrix K corresponding to n points x_1,...,x_n in R^d. In particular, we consider the estimating the sum of kernel matrix entries, along with its top eigenvalue and eigenvector. These are some of the most basic problems defined over kernel matrices. We show that the sum of matrix entries can be estimated up to a multiplicative factor of 1+epsilon in time sublinear in n and linear in d for many popular kernel functions, including the Gaussian, exponential, and rational quadratic kernels. For these kernels, we also show that the top eigenvalue (and a witnessing approximate eigenvector) can be approximated to a multiplicative factor of 1+epsilon in time sub-quadratic in n and linear in d. Our algorithms represent significant advances in the best known runtimes for these problems. They leverage the positive definiteness of the kernel matrix, along with a recent line of work on efficient kernel density estimation. 

   more » « less
4. Almost Everywhere Behavior of Functions According to Partition Measures

   https://doi.org/10.1017/fms.2023.130  

   Chan, William; Jackson, Stephen; Trang, Nam (January 2024, Forum of Mathematics, Sigma)

   Abstract This paper will study almost everywhere behaviors of functions on partition spaces of cardinals possessing suitable partition properties. Almost everywhere continuity and monotonicity properties for functions on partition spaces will be established. These results will be applied to distinguish the cardinality of certain subsets of the power set of partition cardinals. The following summarizes the main results proved under suitable partition hypotheses.•If$$\kappa $$is a cardinal,$$\epsilon < \kappa $$,$${\mathrm {cof}}(\epsilon ) = \omega $$,$$\kappa \rightarrow _* (\kappa )^{\epsilon \cdot \epsilon }_2$$and$$\Phi : [\kappa ]^\epsilon _* \rightarrow \mathrm {ON}$$, then$$\Phi $$satisfies the almost everywhere short length continuity property: There is a club$$C \subseteq \kappa $$and a$$\delta < \epsilon $$so that for all$$f,g \in [C]^\epsilon _*$$, if$$f \upharpoonright \delta = g \upharpoonright \delta $$and$$\sup (f) = \sup (g)$$, then$$\Phi (f) = \Phi (g)$$.•If$$\kappa $$is a cardinal,$$\epsilon $$is countable,$$\kappa \rightarrow _* (\kappa )^{\epsilon \cdot \epsilon }_2$$holds and$$\Phi : [\kappa ]^\epsilon _* \rightarrow \mathrm {ON}$$, then$$\Phi $$satisfies the strong almost everywhere short length continuity property: There is a club$$C \subseteq \kappa $$and finitely many ordinals$$\delta _0, ..., \delta _k \leq \epsilon $$so that for all$$f,g \in [C]^\epsilon _*$$, if for all$$0 \leq i \leq k$$,$$\sup (f \upharpoonright \delta _i) = \sup (g \upharpoonright \delta _i)$$, then$$\Phi (f) = \Phi (g)$$.•If$$\kappa $$satisfies$$\kappa \rightarrow _* (\kappa )^\kappa _2$$,$$\epsilon \leq \kappa $$and$$\Phi : [\kappa ]^\epsilon _* \rightarrow \mathrm {ON}$$, then$$\Phi $$satisfies the almost everywhere monotonicity property: There is a club$$C \subseteq \kappa $$so that for all$$f,g \in [C]^\epsilon _*$$, if for all$$\alpha < \epsilon $$,$$f(\alpha ) \leq g(\alpha )$$, then$$\Phi (f) \leq \Phi (g)$$.•Suppose dependent choice ($$\mathsf {DC}$$),$${\omega _1} \rightarrow _* ({\omega _1})^{\omega _1}_2$$and the almost everywhere short length club uniformization principle for$${\omega _1}$$hold. Then every function$$\Phi : [{\omega _1}]^{\omega _1}_* \rightarrow {\omega _1}$$satisfies a finite continuity property with respect to closure points: Let$$\mathfrak {C}_f$$be the club of$$\alpha < {\omega _1}$$so that$$\sup (f \upharpoonright \alpha ) = \alpha $$. There is a club$$C \subseteq {\omega _1}$$and finitely many functions$$\Upsilon _0, ..., \Upsilon _{n - 1} : [C]^{\omega _1}_* \rightarrow {\omega _1}$$so that for all$$f \in [C]^{\omega _1}_*$$, for all$$g \in [C]^{\omega _1}_*$$, if$$\mathfrak {C}_g = \mathfrak {C}_f$$and for all$$i < n$$,$$\sup (g \upharpoonright \Upsilon _i(f)) = \sup (f \upharpoonright \Upsilon _i(f))$$, then$$\Phi (g) = \Phi (f)$$.•Suppose$$\kappa $$satisfies$$\kappa \rightarrow _* (\kappa )^\epsilon _2$$for all$$\epsilon < \kappa $$. For all$$\chi < \kappa $$,$$[\kappa ]^{<\kappa }$$does not inject into$${}^\chi \mathrm {ON}$$, the class of$$\chi $$-length sequences of ordinals, and therefore,$$|[\kappa ]^\chi | < |[\kappa ]^{<\kappa }|$$. As a consequence, under the axiom of determinacy$$(\mathsf {AD})$$, these two cardinality results hold when$$\kappa $$is one of the following weak or strong partition cardinals of determinacy:$${\omega _1}$$,$$\omega _2$$,$$\boldsymbol {\delta }_n^1$$(for all$$1 \leq n < \omega $$) and$$\boldsymbol {\delta }^2_1$$(assuming in addition$$\mathsf {DC}_{\mathbb {R}}$$). 

   more » « less
5. Uniform stabilization in Besov spaces with arbitrary decay rates of the magnetohydrodynamic system by finite-dimensional interior localized static feedback controllers

   https://doi.org/10.1007/s40687-024-00490-7  

   Lasiecka, Irena; Priyasad, Buddhika; Triggiani, Roberto (March 2025, Research in the Mathematical Sciences)

   We consider the d-dimensional MagnetoHydroDynamics (MHD) system defined on a sufficiently smooth bounded domain, with homogeneous boundary conditions, and subject to external sources assumed to cause instability. The initial conditions for both fluid and magnetic equations are taken of low regularity. We then seek to uniformly stabilize such MHD system in the vicinity of an unstable equilibrium pair, in the critical setting of correspondingly low regularity spaces, by means of explicitly constructed, static, feedback controls, which are localized on an arbitrarily small interior subdomain. In additional, they will be minimal in number. The resulting space of well-posedness and stabilization is a suitable product space $$\displaystyle \widetilde{\textbf{B}}^{2- ^{2}\!/_{p}}_{q,p}(\Omega )\times \widetilde{\textbf{B}}^{2- ^{2}\!/_{p}}_{q,p}(\Omega ), \, 1< p < \frac{2q}{2q-1}, \, q > d,$$ of tight Besov spaces for the fluid velocity component and the magnetic field component (each “close” to $$\textbf{L}^3(\Omega )$$ for $d = 3$). Showing maximal $L^p$-regularity up to $$T = \infty$$ for the feedback stabilized linear system is critical for the analysis of well-posedness and stabilization of the feedback nonlinear problem. 

   more » « less