More Like this

1. Robust Wirtinger Flow Algorithm for Channel Coded Blind Demixing

   https://doi.org/10.1109/ICC45855.2022.9838429  

   Jalali, Amin ; Shi, Yuanming ; Ding, Zhi ( March 2022 , IEEE International Conference on Communications)

   As applications of Internet-of-things (IoT) rapidly expand, unscheduled multiple user access with low latency and low cost communication is attracting growing more interests. To recover the multiple uplink signals without strict access control under dynamic co-channel interference environment, the problem of blind demixing emerges as an important obstacle for us to overcome. Without channel state information, successful blind demixing can recover multiple user signals more effectively by leveraging prior information on signal characteristics such as constellations and distribution. This work studies how forward error correction (FEC) codes in Galois Field can generate more effective blind demixing algorithms. We propose a constrained Wirtinger flow algorithm by defining a valid signal set based on FEC codewords. Specifically, targeting the popular polar codes for FEC of short IoT packets, we introduce signal projections within iterations of Wirtinger Flow based on FEC code information. Simulation results demonstrate stronger robustness of the proposed algorithm against noise and practical obstacles and also faster convergence rate compared to regular Wirtinger flow algorithm. 

   more » « less
2. Convergent Bregman Plug-and-Play Image Restoration for Poisson Inverse Problems

   Hurault, Samuel ; Kamilov, Ulugbek S. ; Leclaire, Arthur ; Papadakis, Nicolas ( December 2023 , Conference on Neural Information Processing Systems (NeurIPS))

   Plug-and-Play (PnP) methods are efficient iterative algorithms for solving ill-posed image inverse problems. PnP methods are obtained by using deep Gaussian denoisers instead of the proximal operator or the gradient-descent step within proximal algorithms. Current PnP schemes rely on data-fidelity terms that have either Lipschitz gradients or closed-form proximal operators, which is not applicable to Poisson inverse problems. Based on the observation that the Gaussian noise is not the adequate noise model in this setting, we propose to generalize PnP using the Bregman Proximal Gradient (BPG) method. BPG replaces the Euclidean distance with a Bregman divergence that can better capture the smoothness properties of the problem. We introduce the Bregman Score Denoiser specifically parametrized and trained for the new Bregman geometry and prove that it corresponds to the proximal operator of a nonconvex potential. We propose two PnP algorithms based on the Bregman Score Denoiser for solving Poisson inverse problems. Extending the convergence results of BPG in the nonconvex settings, we show that the proposed methods converge, targeting stationary points of an explicit global functional. Experimental evaluations conducted on various Poisson inverse problems validate the convergence results and showcase effective restoration performance. 

   more » « less
3. On the Cryptographic Hardness of Learning Single Periodic Neurons

   Min Jae Song ; Ilias Zadik ; Joan Bruna ( December 2021 , Advances in neural information processing systems)

   We show a simple reduction which demonstrates the cryptographic hardness of learning a single periodic neuron over isotropic Gaussian distributions in the pres- ence of noise. More precisely, our reduction shows that any polynomial-time algorithm (not necessarily gradient-based) for learning such functions under small noise implies a polynomial-time quantum algorithm for solving worst-case lattice problems, whose hardness form the foundation of lattice-based cryptography. Our core hard family of functions, which are well-approximated by one-layer neural networks, take the general form of a univariate periodic function applied to an affine projection of the data. These functions have appeared in previous seminal works which demonstrate their hardness against gradient-based (Shamir’18), and Statisti- cal Query (SQ) algorithms (Song et al.’17). We show that if (polynomially) small noise is added to the labels, the intractability of learning these functions applies to all polynomial-time algorithms, beyond gradient-based and SQ algorithms, under the aforementioned cryptographic assumptions. Moreover, we demonstrate the necessity of noise in the hardness result by designing a polynomial-time algorithm for learning certain families of such functions under exponentially small adversarial noise. Our proposed algorithm is not a gradient-based or an SQ algorithm, but is rather based on the celebrated Lenstra-Lenstra-Lovász (LLL) lattice basis reduction algorithm. Furthermore, in the absence of noise, this algorithm can be directly applied to solve CLWE detection (Bruna et al.’21) and phase retrieval with an optimal sample complexity of d + 1 samples. In the former case, this improves upon the quadratic-in-d sample complexity required in (Bruna et al.’21). 

   more » « less
4. On the Cryptographic Hardness of Learning Single Periodic Neurons

   Song, Min Jae ; Zadik, Ilias ; Bruna, Joan ( December 2021 , Advances in neural information processing systems)

   null (Ed.)

   Abstract We show a simple reduction which demonstrates the cryptographic hardness of learning a single periodic neuron over isotropic Gaussian distributions in the presence of noise. More precisely, our reduction shows that any polynomial-time algorithm (not necessarily gradientbased) for learning such functions under small noise implies a polynomial-time quantum algorithm for solving worst-case lattice problems, whose hardness form the foundation of lattice-based cryptography. Our core hard family of functions, which are well-approximated by one-layer neural networks, take the general form of a univariate periodic function applied to an affine projection of the data. These functions have appeared in previous seminal works which demonstrate their hardness against gradient-based (Shamir’18), and Statistical Query (SQ) algorithms (Song et al.’17). We show that if (polynomially) small noise is added to the labels, the intractability of learning these functions applies to all polynomial-time algorithms, beyond gradient-based and SQ algorithms, under the aforementioned cryptographic assumptions. Moreover, we demonstrate the necessity of noise in the hardness result by designing a polynomial-time algorithm for learning certain families of such functions under exponentially small adversarial noise. Our proposed algorithm is not a gradient-based or an SQ algorithm, but is rather based on the celebrated Lenstra-Lenstra-Lovász (LLL) lattice basis reduction algorithm. Furthermore, in the absence of noise, this algorithm can be directly applied to solve CLWE detection (Bruna et al.’21) and phase retrieval with an optimal sample complexity of d + 1 samples. In the former case, this improves upon the quadratic-in-d sample complexity required in (Bruna et al.’21). 

   more » « less
5. Wirtinger Flow Meets Constant Modulus Algorithm: Revisiting Signal Recovery for Grant-Free Access

   Feres, Carlos ; Ding, Zhi ( January 2021 , IEEE transactions on signal processing)

   null (Ed.)

   In this work, we analyze the convergence of constant modulus algorithm (CMA) in blindly recovering multiple signals to facilitate grant-free wireless access. The CMA typically solves a non-convex problem by utilizing stochastic gradient descent. The iterative convergence of CMA can be affected by additive channel noise and finite number of samples, which is a problem not fully investigated previously. We point out the strong similarity between CMA and the Wirtinger Flow (WF) algorithm originally proposed for Phase retrieval. In light of the convergence proof of WF under limited data samples, we adopt the WF algorithm to implement CMA-based blind signal recovery. We generalize the convergence analysis of WF in the context of CMA-based blind signal recovery. Numerical simulation results also corroborate the analysis. 

   more » « less