Journal: Sampling Theory, Signal Processing, and Data Analysis

Abbreviation

Publisher

Springer

Journal Volumes

ISSN

Description

Filters

2022 - 20243
Reset filters

Search Results

Publications1 - 3 of 3
  • On the connection between uniqueness from samples and stability in Gabor phase retrieval
    Item type: Journal Article
    Alaifari, Rima; Bartolucci, Francesca; Steinerberger, Stefan; et al. (2024)
    Sampling Theory, Signal Processing, and Data Analysis
    Gabor phase retrieval is the problem of reconstructing a signal from only the magnitudes of its Gabor transform. Previous findings suggest a possible link between unique solvability of the discrete problem (recovery from measurements on a lattice) and stability of the continuous problem (recovery from measurements on an open subset of R2). In this paper, we close this gap by proving that such a link cannot be made. More precisely, we establish the existence of functions which break uniqueness from samples without affecting stability of the continuous problem. Furthermore, we prove the novel result that counterexamples to unique recovery from samples are dense in L2(R) . Finally, we develop an intuitive argument on the connection between directions of instability in phase retrieval and certain Laplacian eigenfunctions associated to small eigenvalues.
  • Community detection with a subsampled semidefinite program
    Item type: Journal Article
    Abdalla, Pedro; Bandeira, Afonso S. (2022)
    Sampling Theory, Signal Processing, and Data Analysis
    Semidefinite programming is an important tool to tackle several problems in data science and signal processing, including clustering and community detection. However, semidefinite programs are often slow in practice, so speed up techniques such as sketching are often considered. In the context of community detection in the stochastic block model, Mixon and Xie (IEEE Trans Inform Theory 67(10): 6832–6840, 2021) have recently proposed a sketching framework in which a semidefinite program is solved only on a subsampled subgraph of the network, giving rise to significant computational savings. In this short paper, we provide a positive answer to a conjecture of Mixon and Xie about the statistical limits of this technique for the stochastic block model with two balanced communities.
  • Dual bounds for the positive definite functions approach to mutually unbiased bases
    Item type: Journal Article
    Bandeira, Afonso S.; Doppelbauer, Nikolaus; Kunisky, Dmitriy (2022)
    Sampling Theory, Signal Processing, and Data Analysis
    A long-standing open problem asks if there can exist 7 mutually unbiased bases (MUBs) in C6, or, more generally, d + 1 MUBs in Cd for any d that is not a prime power. Recent work of Proc Am Math Soc 146(3), 1143–1150 (2018) proposed an application of the method of positive definite functions (a relative of Delsarte’s method in coding theory and Lovász’s semidefinite programming relaxation of the independent set problem) as a means of answering this question in the negative. Namely, they ask whether there exists a polynomial of a unitary matrix input satisfying various properties which, through the method of positive definite functions, would show that 7 MUBs cannot exist in C6. Using a convex duality argument, we prove that there is no such polynomial of degree at most 6. We also propose a general dual certificate which we conjecture to certify that this method can never show that there exist strictly fewer than d + 1 MUBs in Cd.
Publications1 - 3 of 3