More Like this

1. A Duality Principle for Groups II: Multi-frames Meet Super-Frames

   https://doi.org/10.1007/s00041-020-09792-0  

   Balan, R.; Dutkay, D.; Han, D.; Larson, D.; Luef, F. (December 2020, Journal of Fourier Analysis and Applications)

   null (Ed.)

   Abstract The duality principle for group representations developed in Dutkay et al. (J Funct Anal 257:1133–1143, 2009), Han and Larson (Bull Lond Math Soc 40:685–695, 2008) exhibits a fact that the well-known duality principle in Gabor analysis is not an isolated incident but a more general phenomenon residing in the context of group representation theory. There are two other well-known fundamental properties in Gabor analysis: the biorthogonality and the fundamental identity of Gabor analysis. The main purpose of this this paper is to show that these two fundamental properties remain to be true for general projective unitary group representations. Moreover, we also present a general duality theorem which shows that that muti-frame generators meet super-frame generators through a dual commutant pair of group representations. Applying it to the Gabor representations, we obtain that $$\{\pi _{\Lambda }(m, n)g_{1} \oplus \cdots \oplus \pi _{\Lambda }(m, n)g_{k}\}_{m, n \in {\mathbb {Z}}^{d}}$$ { π Λ ( m , n ) g 1 ⊕ ⋯ ⊕ π Λ ( m , n ) g k } m , n ∈ Z d is a frame for $$L^{2}({\mathbb {R}}\,^{d})\oplus \cdots \oplus L^{2}({\mathbb {R}}\,^{d})$$ L 2 ( R d ) ⊕ ⋯ ⊕ L 2 ( R d ) if and only if $$\cup _{i=1}^{k}\{\pi _{\Lambda ^{o}}(m, n)g_{i}\}_{m, n\in {\mathbb {Z}}^{d}}$$ ∪ i = 1 k { π Λ o ( m , n ) g i } m , n ∈ Z d is a Riesz sequence, and $$\cup _{i=1}^{k} \{\pi _{\Lambda }(m, n)g_{i}\}_{m, n\in {\mathbb {Z}}^{d}}$$ ∪ i = 1 k { π Λ ( m , n ) g i } m , n ∈ Z d is a frame for $$L^{2}({\mathbb {R}}\,^{d})$$ L 2 ( R d ) if and only if $$\{\pi _{\Lambda ^{o}}(m, n)g_{1} \oplus \cdots \oplus \pi _{\Lambda ^{o}}(m, n)g_{k}\}_{m, n \in {\mathbb {Z}}^{d}}$$ { π Λ o ( m , n ) g 1 ⊕ ⋯ ⊕ π Λ o ( m , n ) g k } m , n ∈ Z d is a Riesz sequence, where $$\pi _{\Lambda }$$ π Λ and $$\pi _{\Lambda ^{o}}$$ π Λ o is a pair of Gabor representations restricted to a time–frequency lattice $$\Lambda $$ Λ and its adjoint lattice $$\Lambda ^{o}$$ Λ o in $${\mathbb {R}}\,^{d}\times {\mathbb {R}}\,^{d}$$ R d × R d . 

   more » « less
2. Constructing many faces in arrangements of lines and segments

   https://doi.org/10.20382/jocg.v14i1a11  

   Wang, Haitao (December 2023, Journal of computational geometry)

   We present new algorithms for computing many faces in arrangements of lines and segments. Given a set $$S$$ of $$n$$ lines (resp., segments) and a set $$P$$ of $$m$$ points in the plane, the problem is to compute the faces of the arrangements of $$S$$ that contain at least one point of $$P$$. For the line case, we give a deterministic algorithm of $$O(m^{2/3}n^{2/3}\log^{2/3} (n/\sqrt{m})+(m+n)\log n)$$ time. This improves the previously best deterministic algorithm [Agarwal, 1990] by a factor of $$\log^{2.22}n$$ and improves the previously best randomized algorithm [Agarwal, Matoušek, and Schwarzkopf, 1998] by a factor of $$\log^{1/3}n$$ in certain cases (e.g., when $$m=\Theta(n)$$). For the segment case, we present a deterministic algorithm of $$O(n^{2/3}m^{2/3}\log n+\tau(n\alpha^2(n)+n\log m+m)\log n)$$ time, where $$\tau=\min\{\log m,\log (n/\sqrt{m})\}$$ and $$\alpha(n)$$ is the inverse Ackermann function. This improves the previously best deterministic algorithm [Agarwal, 1990] by a factor of $$\log^{2.11}n$$ and improves the previously best randomized algorithm [Agarwal, Matoušek, and Schwarzkopf, 1998] by a factor of $$\log n$$ in certain cases (e.g., when $$m=\Theta(n)$$). We also give a randomized algorithm of $$O(m^{2/3}K^{1/3}\log n+\tau(n\alpha(n)+n\log m+m)\log n\log K)$$ expected time, where $$K$$ is the number of intersections of all segments of $$S$$. In addition, we consider the query version of the problem, that is, preprocess $$S$$ to compute the face of the arrangement of $$S$$ that contains any given query point. We present new results that improve the previous work for both the line and the segment cases. In particulary, for the line case, we build a data structure of $$O(n\log n)$$ space in $$O(n\log n)$$ randomized time, so that the face containing the query point can be obtained in $$O(\sqrt{n\log n})$$ time with high probability (more specifically, the query returns a binary search tree representing the face so that standard binary-search-based queries on the face can be handled in $$O(\log n)$$ time each and the face itself can be output explicitly in time linear in its size). 

   more » « less
3. Characterizing Schwarz maps by tracial inequalities

   https://doi.org/10.1007/s11005-023-01636-4  

   Carlen, Eric; Müller-Hermes, Alexander (February 2023, Letters in Mathematical Physics)

   Abstract Let $$\phi $$ ϕ be a positive map from the $$n\times n$$ n × n matrices $$\mathcal {M}_n$$ M n to the $$m\times m$$ m × m matrices $$\mathcal {M}_m$$ M m . It is known that $$\phi $$ ϕ is 2-positive if and only if for all $$K\in \mathcal {M}_n$$ K ∈ M n and all strictly positive $$X\in \mathcal {M}_n$$ X ∈ M n , $$\phi (K^*X^{-1}K) \geqslant \phi (K)^*\phi (X)^{-1}\phi (K)$$ ϕ ( K ∗ X - 1 K ) ⩾ ϕ ( K ) ∗ ϕ ( X ) - 1 ϕ ( K ) . This inequality is not generally true if $$\phi $$ ϕ is merely a Schwarz map. We show that the corresponding tracial inequality $${{\,\textrm{Tr}\,}}[\phi (K^*X^{-1}K)] \geqslant {{\,\textrm{Tr}\,}}[\phi (K)^*\phi (X)^{-1}\phi (K)]$$ Tr [ ϕ ( K ∗ X - 1 K ) ] ⩾ Tr [ ϕ ( K ) ∗ ϕ ( X ) - 1 ϕ ( K ) ] holds for a wider class of positive maps that is specified here. We also comment on the connections of this inequality with various monotonicity statements that have found wide use in mathematical physics, and apply it, and a close relative, to obtain some new, definitive results. 

   more » « less
4. Improved Lower Bounds for 3-Query Matching Vector Codes

   https://doi.org/10.4230/LIPIcs.ITCS.2025.2  

   Aggarwal, Divesh; Dutta, Pranjal; Li, Zeyong; Obremski, Maciej; Saraogi, Sidhant (January 2025, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Meka, Raghu (Ed.)

   A Matching Vector (MV) family modulo a positive integer m ≥ 2 is a pair of ordered lists U = (u_1, ⋯, u_K) and V = (v_1, ⋯, v_K) where u_i, v_j ∈ ℤ_m^n with the following property: for any i ∈ [K], the inner product ⟨u_i, v_i⟩ = 0 mod m, and for any i ≠ j, ⟨u_i, v_j⟩ ≠ 0 mod m. An MV family is called r-restricted if inner products ⟨u_i, v_j⟩, for all i,j, take at most r different values. The r-restricted MV families are extremely important since the only known construction of constant-query subexponential locally decodable codes (LDCs) are based on them. Such LDCs constructed via matching vector families are called matching vector codes. Let MV(m,n) (respectively MV(m, n, r)) denote the largest K such that there exists an MV family (respectively r-restricted MV family) of size K in ℤ_m^n. Such a MV family can be transformed in a black-box manner to a good r-query locally decodable code taking messages of length K to codewords of length N = m^n. For small prime m, an almost tight bound MV(m,n) ≤ O(m^{n/2}) was first shown by Dvir, Gopalan, Yekhanin (FOCS'10, SICOMP'11), while for general m, the same paper established an upper bound of O(m^{n-1+o_m(1)}), with o_m(1) denoting a function that goes to zero when m grows. For any arbitrary constant r ≥ 3 and composite m, the best upper bound till date on MV(m,n,r) is O(m^{n/2}), is due to Bhowmick, Dvir and Lovett (STOC'13, SICOMP'14).In a breakthrough work, Alrabiah, Guruswami, Kothari and Manohar (STOC'23) implicitly improve this bound for 3-restricted families to MV(m, n, 3) ≤ O(m^{n/3}). In this work, we present an upper bound for r = 3 where MV(m,n,3) ≤ m^{n/6 +O(log n)}, and as a result, any 3-query matching vector code must have codeword length of N ≥ K^{6-o(1)}. 

   more » « less
5. The Splitting Theorem and topology of noncompact spaces with nonnegative N-Bakry Émery Ricci curvature

   https://doi.org/10.1090/proc/15240  

   Lim, Alice (August 2021, Proceedings of the American Mathematical Society)

   In this paper, we generalize topological results known for noncompact manifolds with nonnegative Ricci curvature to spaces with nonnegative N N -Bakry Émery Ricci curvature. We study the Splitting Theorem and a property called the geodesic loops to infinity property in relation to spaces with nonnegative N N -Bakry Émery Ricci curvature. In addition, we show that if M n M^n is a complete, noncompact Riemannian manifold with nonnegative N N -Bakry Émery Ricci curvature where N > n N>n , then H n − 1 ( M , Z ) H_{n-1}(M,\mathbb {Z}) is 0 0 . 

   more » « less