Special Session 97: New Advances in Structured Signal Recovery

Weighted Riemannian Optimization for Phase Retrieval

Jian-Feng Cai The Hong Kong University of Science and Technology Hong Kong Co-Author(s):    Jiayi Li, Huiping Li

Abstract: We investigate the problem of generalized phase retrieval, which entails reconstructing a signal from its phaseless samples. We demonstrate that several well-known phase retrieval algorithms actually solve the least-squares fitting of lifted linear equations within the manifold of rank-1 matrices, using different Riemannian metrics on the manifold. However, these metrics only permit a stable and distinctly non-isometric embedding of rank-1 matrices, leading to linear convergence with a notably slow rate. To accelerate the convergence, we introduce a new metric on the rank-1 matrix manifold that enables an almost isometric embedding of these matrices. We propose a Riemannian gradient descent (RGD) algorithm, named Weighted RGD (WRGD), with this new metric to solve the phase retrieval problem. Due to the near isometric nature of this metric, we demonstrate that our WRGD, initialized via the spectral method, achieves linear convergence to the target signal at an enhanced rate.

A Generalized Matrix Separation Problem

Xuemei Chen University of North Carolina Wilmington USA Co-Author(s):

Abstract: The problem of separating a known matrix into its low rank and sparse components have found numerous applications in imaging, multimedia processing, statistical modeling, etc. In this talk we will explore this problem in a more complicated setting where the sparse component has been masked by a linear transformation. This problem was motivated by an electrodermal activity signal decomposition problem, but we believe it has a wider appeal.

Conjugate Phase Retrieval in Shift-invariant Spaces

Cheng Cheng SUN YAT-SEN University Peoples Rep of China Co-Author(s):

Abstract: Conjugate phase retrieval considers the recovery of a function, up to a unimodular constant and conjugation, from its phaseless measurements. In this talk, I will introduce some results on conjugate phase retrieval in shift-invariant spaces. We first consider the conjugate phase retrieval in a shift-invariant space generated by a Gaussian, and show that a function in the shift-invariant space generated by Gaussian can be uniquely determined, up to a unimodular constant and conjugation, from its phaseless Hermite samples on a discrete set.

Exponential type bases in L^2(\mu) with phase funtions

Xiaoye Fu Central China Normal University Peoples Rep of China Co-Author(s):    Ting Zhou

Abstract: Given a finite Borel measure $\mu$ on $\Bbb{R}^d$, we give a characterization on the existence of a phase function $\varphi$ such that $L^2(\mu)$ admits an orthogonal basis/a frame/a Riesz basis of exponential type $E(\Lambda,\varphi)=\{e^{2\pi i \langle\lambda,\varphi(x)\rangle}:\lambda\in\Lambda\},$ according to the type of $\mu$: discrete, singularly and absolutely continuous. We show that if $\mu$ is an infinite discrete measure or a finite discrete measure with non-equal probability weights, then $L^2(\mu)$ can not admit any $E(\Lambda,\varphi)$ as an orthogonal basis. We also prove that $L^2(\mu)$ can admit some $E(\Lambda,\varphi)$ as an orthogonal basis if $\mu$ is one of the following four types (i) a self-affine measure generated by an equal probability IFS with no-overlap condition; (ii) the Lebesgue measure restricted on a bounded open set ; (iii) a positive and finite absolutely continuous measure with respect to Lebesgue measure on $\Bbb{R}$; (iv) a finite discrete measure with equal probability weights. Particularly, for the product of two finite Borel measures $\mu\subseteq \Bbb{R}^m$ and $\nu\subseteq\Bbb{R}^n$, we study the relationship on the existence of orthogonal bases in the form of $E(\Lambda,\varphi)$ between in $L^2(\mu\times\nu)$ and in $L^2(\mu)$ and $L^2(\nu)$ according to whether $\Lambda$ or $\varphi$ has a product structure (i.e. $\Lambda=\Lambda_1\times\Lambda_2$ or $\varphi=\varphi_1\times\varphi_2$) or not.

Learning Operators with Stochastic Gradient Descent in General Hilbert Spaces

Shi Lei Fudan University Peoples Rep of China Co-Author(s):

Abstract: This talk investigates leveraging stochastic gradient descent (SGD) to learn operators between general Hilbert spaces. We propose weak and strong regularity conditions for the target operator to depict its intrinsic structure and complexity. Under these conditions, we establish upper bounds for convergence rates of the SGD algorithm and conduct a minimax lower bound analysis, further illustrating that our convergence analysis and regularity conditions quantitatively characterize the tractability of solving operator learning problems using the SGD algorithm. It is crucial to highlight that our convergence analysis is still valid for nonlinear operator learning. We show that the SGD estimator will converge to the best linear approximation of the nonlinear target operator. Moreover, applying our analysis to operator learning problems based on vector-valued and real-valued reproducing kernel Hilbert spaces yields new convergence results, thereby refining the conclusions of existing literature.

Sparse Recovery using Expanders via Hard Thresholding Algorithm

Peng Li Lanzhou University Peoples Rep of China Co-Author(s):

Abstract: Expanders play an important role in binary sensors, network measurement, and distributed storage, etc. Via expanders measurements, we propose the expander normalized heavy ball hard thresholding algorithm (ENHB-HT) based on the expander iterative hard thresholding (E-IHT) algorithm. We provide a convergence analysis of ENHB-HT, and it turns out that ENHB-HT can recover an s-sparse signal if the binary sparse measurement matrix A satisfies some mild conditions. Numerical experiments are simulated to support our two main theorems which describe the convergence rate and the accuracy of the proposed algorithm. Simulations are also performed to compare the performance of ENHB-HT and several existing algorithms under different types of noise, the empirical results demonstrate that our algorithm outperforms a few existing ones in the presence of outliers.

Uniqueness of STFT Phase Retrieval for wide band functions

Kasso Okoudjou Tufts University USA Co-Author(s):    Shuang Guan and Kasso Okoudjou

Abstract: We consider the phase retrieval problem for the short-time Fourier transform (STFT). We establish new results on the reconstruction of wide-band signals up to a global phase factor from only the magnitude of their measurements in the time-frequency domain. The proof of our main result relies on the factorization of functions in the Hardy space on the unit disk, the fractional short-time Fourier transform, and an identity theorem for holomorphic functions.

Leave-One-Out Analysis for Nonconvex Robust Matrix Completion with General Thresholding Functions

Ke Wei Fudan University Peoples Rep of China Co-Author(s):    Tianming Wang

Abstract: We study the problem of robust matrix completion (RMC), where the partially observed entries of an underlying low-rank matrix is corrupted by sparse noise. Existing analysis of the non-convex methods for this problem either requires the explicit but empirically redundant regularization in the algorithm or requires sample splitting in the analysis. In this paper, we consider a simple yet efficient nonconvex method which alternates between a projected gradient step for the low-rank part and a thresholding step for the sparse noise part. Inspired by leave-one out analysis for low rank matrix completion, it is established that the method can achieve linear convergence for a general class of thresholding functions, including for example soft-thresholding and SCAD. To the best of our knowledge, this is the first leave-one-out analysis on a nonconvex method for RMC. Additionally, when applying our result to low rank matrix completion, it improves the sampling complexity of existing result for the singular value projection method.

Sparse Phase Retrieval under Fourier-based Measurements

Yu Xia Hangzhou Normal University Peoples Rep of China Co-Author(s):

Abstract: We consider the sparse phase retrieval problem, that is, recovering an unknown $s$-sparse signal from the intensity-only measurements. Specically, we focus on the problem of recovering $x$ from the observations that are convoluted with some specfic kernel, it can also be considered as masked Fourier measurements. This model is motivated by real-world applications in optics and communications. If the convolutional kernel is generated by a random Gaussian vector and the number of subsampled measurements is on the order of $s\cdot polylog(n)$, one can recover $x$ up to a global phase. Here we discuss the behavior of sparse phase retrieval under more realistic measurements, as opposed to independent Gaussian measurements.