An official website of the United States government
We develop a general framework for finding approximately-optimal preconditioners for solving linear systems. Leveraging this framework we obtain improved runtimes for fundamental preconditioning and linear system solving problems including the following. \begin{itemize} \item \textbf{Diagonal preconditioning.} We give an algorithm which, given positive definite $$\mathbf{K} \in \mathbb{R}^{d \times d}$$ with $$\mathrm{nnz}(\mathbf{K})$$ nonzero entries, computes an $$\epsilon$$-optimal diagonal preconditioner in time $$\widetilde{O}(\mathrm{nnz}(\mathbf{K}) \cdot \mathrm{poly}(\kappa^\star,\epsilon^{-1}))$$, where $$\kappa^\star$$ is the optimal condition number of the rescaled matrix. \item \textbf{Structured linear systems.} We give an algorithm which, given $$\mathbf{M} \in \mathbb{R}^{d \times d}$$ that is either the pseudoinverse of a graph Laplacian matrix or a constant spectral approximation of one, solves linear systems in $$\mathbf{M}$$ in $$\widetilde{O}(d^2)$$ time. \end{itemize} Our diagonal preconditioning results improve state-of-the-art runtimes of $$\Omega(d^{3.5})$$ attained by general-purpose semidefinite programming, and our solvers improve state-of-the-art runtimes of $$\Omega(d^{\omega})$$ where $$\omega > 2.3$$ is the current matrix multiplication constant. We attain our results via new algorithms for a class of semidefinite programs (SDPs) we call \emph{matrix-dictionary approximation SDPs}, which we leverage to solve an associated problem we call \emph{matrix-dictionary recovery}.
more »
« less
Inverting spectrogram measurements via aliased Wigner distribution deconvolution and angular synchronization
Abstract We propose a two-step approach for reconstructing a signal $$\textbf x\in \mathbb{C}^d$$ from subsampled discrete short-time Fourier transform magnitude (spectogram) measurements: first, we use an aliased Wigner distribution deconvolution approach to solve for a portion of the rank-one matrix $$\widehat{\textbf{x}}\widehat{\textbf{x}}^{*}.$$ Secondly, we use angular synchronization to solve for $$\widehat{\textbf{x}}$$ (and then for $$\textbf{x}$$ by Fourier inversion). Using this method, we produce two new efficient phase retrieval algorithms that perform well numerically in comparison to standard approaches and also prove two theorems; one which guarantees the recovery of discrete, bandlimited signals $$\textbf{x}\in \mathbb{C}^{d}$$ from fewer than $$d$$ short-time Fourier transform magnitude measurements and another which establishes a new class of deterministic coded diffraction pattern measurements which are guaranteed to allow efficient and noise robust recovery.
more »
« less
- Award ID(s):
- 1912706
- PAR ID:
- 10148906
- Date Published:
- Journal Name:
- Information and Inference: A Journal of the IMA
- ISSN:
- 2049-8764
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
null (Ed.)In this paper we consider the following sparse recovery problem. We have query access to a vector đ± â â^N such that xÌ = đ đ± is k-sparse (or nearly k-sparse) for some orthogonal transform đ . The goal is to output an approximation (in an đâ sense) to xÌ in sublinear time. This problem has been well-studied in the special case that đ is the Discrete Fourier Transform (DFT), and a long line of work has resulted in sparse Fast Fourier Transforms that run in time O(k â polylog N). However, for transforms đ other than the DFT (or closely related transforms like the Discrete Cosine Transform), the question is much less settled. In this paper we give sublinear-time algorithms - running in time poly(k log(N)) - for solving the sparse recovery problem for orthogonal transforms đ that arise from orthogonal polynomials. More precisely, our algorithm works for any đ that is an orthogonal polynomial transform derived from Jacobi polynomials. The Jacobi polynomials are a large class of classical orthogonal polynomials (and include Chebyshev and Legendre polynomials as special cases), and show up extensively in applications like numerical analysis and signal processing. One caveat of our work is that we require an assumption on the sparsity structure of the sparse vector, although we note that vectors with random support have this property with high probability. Our approach is to give a very general reduction from the k-sparse sparse recovery problem to the 1-sparse sparse recovery problem that holds for any flat orthogonal polynomial transform; then we solve this one-sparse recovery problem for transforms derived from Jacobi polynomials. Frequently, sparse FFT algorithms are described as implementing such a reduction; however, the technical details of such works are quite specific to the Fourier transform and moreover the actual implementations of these algorithms do not use the 1-sparse algorithm as a black box. In this work we give a reduction that works for a broad class of orthogonal polynomial families, and which uses any 1-sparse recovery algorithm as a black box.more » « less
-
Let\Sigmabe a strictly convex, compact patch of aC^{2}hypersurface in\mathbb{R}^{n}, with non-vanishing Gaussian curvature and surface measured\sigmainduced by the Lebesgue measure in\mathbb{R}^{n}. The MizohataâTakeuchi conjecture states that \int |\widehat{g d\sigma}|^{2} w \leq C \|Xw\|_{\infty} \int |g|^{2} for allg\in L^{2}(\Sigma)and all weightsw \colon \mathbb{R}^{n}\rightarrow [0,+\infty), whereXdenotes theX-ray transform. As partial progress towards the conjecture, we show, as a straightforward consequence of recently-established decoupling inequalities, that for every\varepsilon>0, there exists a positive constantC_{\varepsilon}, which depends only on\Sigmaand\varepsilon, such that for allR \geq 1and all weightsw \colon \mathbb{R}^{n}\rightarrow [0,+\infty), we have \int_{B_R}|\widehat{g d\sigma}|^{2} w \leq C_{\varepsilon} R^{\varepsilon} \sup_{T} \Big(\int_{T} w^{(n+1)/2}\Big)^{2/(n+1)}\int |g|^{2}, whereTranges over the family of tubes in\mathbb{R}^{n}of dimensionsR^{1/2}\times \cdots \times R^{1/2}\times R. From this we deduce the MizohataâTakeuchi conjecture with anR^{(n-1)/(n+1)}-loss; i.e., that \int_{B_R}|\widehat{g d\sigma}|^{2} w \leq C_{\varepsilon} R^{\frac{n-1}{n+1}+ \varepsilon}\|Xw\|_{\infty} \int |g|^{2} for any ballB_{R}of radiusRand any\varepsilon>0. The power(n-1)/(n+1)here cannot be replaced by anything smaller unless properties of\widehat{g d\sigma}beyond âdecoupling axiomsâ are exploited. We also provide estimates which improve this inequality under various conditions on the weight, and discuss some new cases where the conjecture holds.more » « less
-
null (Ed.)Abstract The classical AronszajnâDonoghue theorem states that for a rank-one perturbation of a self-adjoint operator (by a cyclic vector) the singular parts of the spectral measures of the original and perturbed operators are mutually singular. As simple direct sum type examples show, this result does not hold for finite rank perturbations. However, the set of exceptional perturbations is pretty small. Namely, for a family of rank $$d$$ perturbations $$A_{\boldsymbol{\alpha }}:= A + {\textbf{B}} {\boldsymbol{\alpha }} {\textbf{B}}^*$$, $${\textbf{B}}:{\mathbb C}^d\to{{\mathcal{H}}}$$, with $${\operatorname{Ran}}{\textbf{B}}$$ being cyclic for $$A$$, parametrized by $$d\times d$$ Hermitian matrices $${\boldsymbol{\alpha }}$$, the singular parts of the spectral measures of $$A$$ and $$A_{\boldsymbol{\alpha }}$$ are mutually singular for all $${\boldsymbol{\alpha }}$$ except for a small exceptional set $$E$$. It was shown earlier by the 1st two authors, see [4], that $$E$$ is a subset of measure zero of the space $$\textbf{H}(d)$$ of $$d\times d$$ Hermitian matrices. In this paper, we show that the set $$E$$ has small Hausdorff dimension, $$\dim E \le \dim \textbf{H}(d)-1 = d^2-1$$.more » « less
-
Abstract We show that if an exact special Lagrangian $$N\subset {\mathbb {C}}^n$$ N â C n has a multiplicity one, cylindrical tangent cone of the form $${\mathbb {R}}^{k}\times {\textbf{C}}$$ R k Ă C where $${\textbf{C}}$$ C is a special Lagrangian cone with smooth, connected link, then this tangent cone is unique provided $${\textbf{C}}$$ C satisfies an integrability condition. This applies, for example, when $${\textbf{C}}= {\textbf{C}}_{HL}^{m}$$ C = C HL m is the Harvey-Lawson $$T^{m-1}$$ T m - 1 cone for $$m\ne 8,9$$ m â 8 , 9 .more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1093/imaiai/iaaa023
