skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.

Explore Research Products in the PAR
It may take a few hours for recently added research products to appear in PAR search results.


Title: Optimally Sparse Representations of Cartoon-Like Cylindrical Data
Sparse representations of multidimensional data have received a significant attention in the literature due to their applications in problems of data restoration and feature extraction. In this paper, we consider an idealized class C2(Z)⊂L2(R3) of 3-dimensional data dominated by surface singularities that are orthogonal to the xy plane. To deal with this type of data, we introduce a new multiscale directional representation called cylindrical shearlets and prove that this new approach achieves superior approximation properties not only with respect to conventional multiscale representations but also with respect to 3-dimensional shearlets and curvelets. Specifically, the N-term approximation fSN obtained by selecting the N largest coefficients of the cylindrical shearlet expansion of a function f∈C(Z) satisfies the asymptotic estimate ∥f−fSN∥22≤cN−2(lnN)3,as N→∞. This is the optimal decay rate, up the logarithmic factor, outperforming 3d wavelet and 3d shearlet approximations which only yield approximation rates of order N−1/2 and N−1 (ignoring logarithmic factors), respectively, on the same type of data.  more » « less
Award ID(s):
1720452
PAR ID:
10276915
Author(s) / Creator(s):
; ; ;
Date Published:
Journal Name:
The Journal of Geometric Analysis
ISSN:
1050-6926
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. ; ; ; (, Forum of Mathematics, Pi)
    We prove in generic situations that the lattice in a tame type induced by the completed cohomology of a $U(3)$ -arithmetic manifold is purely local, that is, only depends on the Galois representation at places above $$p$$ . This is a generalization to $$\text{GL}_{3}$$ of the lattice conjecture of Breuil. In the process, we also prove the geometric Breuil–Mézard conjecture for (tamely) potentially crystalline deformation rings with Hodge–Tate weights $(2,1,0)$ as well as the Serre weight conjectures of Herzig [‘The weight in a Serre-type conjecture for tame $$n$$ -dimensional Galois representations’, Duke Math. J.   149 (1) (2009), 37–116] over an unramified field extending the results of Le et al. [‘Potentially crystalline deformation 3985 rings and Serre weight conjectures: shapes and shadows’, Invent. Math.   212 (1) (2018), 1–107]. We also prove results in modular representation theory about lattices in Deligne–Lusztig representations for the group $$\text{GL}_{3}(\mathbb{F}_{q})$$ . 
    more » « less
  2. ; ; ; ; (, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022))
    Chakrabarti, Amit; Swamy, Chaitanya (Ed.)
    A Boolean maximum constraint satisfaction problem, Max-CSP(f), is specified by a predicate f:{-1,1}^k → {0,1}. An n-variable instance of Max-CSP(f) consists of a list of constraints, each of which applies f to k distinct literals drawn from the n variables. For k = 2, Chou, Golovnev, and Velusamy [Chou et al., 2020] obtained explicit ratios characterizing the √ n-space streaming approximability of every predicate. For k ≥ 3, Chou, Golovnev, Sudan, and Velusamy [Chou et al., 2022] proved a general dichotomy theorem for √ n-space sketching algorithms: For every f, there exists α(f) ∈ (0,1] such that for every ε > 0, Max-CSP(f) is (α(f)-ε)-approximable by an O(log n)-space linear sketching algorithm, but (α(f)+ε)-approximation sketching algorithms require Ω(√n) space. In this work, we give closed-form expressions for the sketching approximation ratios of multiple families of symmetric Boolean functions. Letting α'_k = 2^{-(k-1)} (1-k^{-2})^{(k-1)/2}, we show that for odd k ≥ 3, α(kAND) = α'_k, and for even k ≥ 2, α(kAND) = 2α'_{k+1}. Thus, for every k, kAND can be (2-o(1))2^{-k}-approximated by O(log n)-space sketching algorithms; we contrast this with a lower bound of Chou, Golovnev, Sudan, Velingker, and Velusamy [Chou et al., 2022] implying that streaming (2+ε)2^{-k}-approximations require Ω(n) space! We also resolve the ratio for the "at-least-(k-1)-1’s" function for all even k; the "exactly-(k+1)/2-1’s" function for odd k ∈ {3,…,51}; and fifteen other functions. We stress here that for general f, the dichotomy theorem in [Chou et al., 2022] only implies that α(f) can be computed to arbitrary precision in PSPACE, and thus closed-form expressions need not have existed a priori. Our analyses involve identifying and exploiting structural "saddle-point" properties of this dichotomy. Separately, for all threshold functions, we give optimal "bias-based" approximation algorithms generalizing [Chou et al., 2020] while simplifying [Chou et al., 2022]. Finally, we investigate the √ n-space streaming lower bounds in [Chou et al., 2022], and show that they are incomplete for 3AND, i.e., they fail to rule out (α(3AND})-ε)-approximations in o(√ n) space. 
    more » « less
  3. ; ; ; (, Proceedings of the American Mathematical Society)
    Motivated by recent work on optimal approximation by polynomials in the unit disk, we consider the following noncommutative approximation problem: for a polynomial f f in d d freely noncommuting arguments, find a free polynomial p n p_n , of degree at most n n , to minimize c n ≔ ‖<#comment/> p n f −<#comment/> 1 ‖<#comment/> 2 c_n ≔\|p_nf-1\|^2 . (Here the norm is the ℓ<#comment/> 2 \ell ^2 norm on coefficients.) We show that c n →<#comment/> 0 c_n\to 0 if and only if f f is nonsingular in a certain nc domain (the row ball), and prove quantitative bounds. As an application, we obtain a new proof of the characterization of polynomials cyclic for the d d -shift. 
    more » « less
  4. ; ; (, Optics Express)
    A new lens capability for three-dimensional (3D) focal control is presented using an optofluidic system consisting ofn × narrayed liquid prisms. Each prism module contains two immiscible liquids in a rectangular cuvette. Using the electrowetting effect, the shape of the fluidic interface can be rapidly adjusted to create its straight profile with the prism’s apex angle. Consequently, an incoming ray is steered at the tilted interface due to the refractive index difference between two liquids. To achieve 3D focal control, individual prisms in the arrayed system are simultaneously modulated, allowing incoming light rays to be spatially manipulated and converged on a focal point located atPfocal(fx,fy,fz) in 3D space. Analytical studies were conducted to precisely predict the prism operation required for 3D focal control. Using three liquid prisms positioned on thex-,y-, and 45°-diagonal axes, we experimentally demonstrated 3D focal tunability of the arrayed optofluidic system, achieving focal tuning along lateral, longitudinal, and axial directions as wide as 0 ≤ fx ≤ 30 mm, 0 ≤ fy ≤ 30 mm, and 500 mm ≤ fz ≤ ∞. This focal tunability of the arrayed system allows for 3D control of the lens’s focusing power, which could not be attained by solid-type optics without the use of bulky and complex mechanical moving components. This innovative lens capability for 3D focal control has potential applications in eye-movement tracking for smart displays, autofocusing of smartphone cameras, or solar tracking for smart photovoltaic systems. 
    more » « less
  5. ; ; ; ; ; (, Proceedings of the ACM on Management of Data)
    In this paper, we consider two fundamental cut approximation problems on large graphs. We prove new lower bounds for both problems that are optimal up to logarithmic factors. The first problem is approximating cuts in balanced directed graphs. In this problem, we want to build a data structure that can provide (1 ± ε)-approximation of cut values on a graph with n vertices. For arbitrary directed graphs, such a data structure requires Ω(n2) bits even for constant ε. To circumvent this, recent works study β-balanced graphs, meaning that for every directed cut, the total weight of edges in one direction is at most β times the total weight in the other direction. We consider the for-each model, where the goal is to approximate each cut with constant probability, and the for-all model, where all cuts must be preserved simultaneously. We improve the previous Ømega(n √β/ε) lower bound in the for-each model to ~Ω (n √β /ε) and we improve the previous Ω(n β/ε) lower bound in the for-all model to Ω(n β/ε2). This resolves the main open questions of (Cen et al., ICALP, 2021). The second problem is approximating the global minimum cut in a local query model, where we can only access the graph via degree, edge, and adjacency queries. We prove an ΩL(min m, m/ε2k R) lower bound for this problem, which improves the previous ΩL(m/k R) lower bound, where m is the number of edges, k is the minimum cut size, and we seek a (1+ε)-approximation. In addition, we show that existing upper bounds with minor modifications match our lower bound up to logarithmic factors. 
    more » « less
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Save / Share this Record
  • Send to Email