More Like this

1. Sparse Recovery for Orthogonal Polynomial Transforms

   https://doi.org/10.4230/LIPIcs.ICALP.2020.58  

   Gilbert, Anna ; Gu, Albert ; Re, Christopher ; Rudra, Atri ; Wootters, Mary ( June 2020 , Leibniz international proceedings in informatics)

   null (Ed.)

   In this paper we consider the following sparse recovery problem. We have query access to a vector 𝐱 ∈ ℝ^N such that x̂ = 𝐅 𝐱 is k-sparse (or nearly k-sparse) for some orthogonal transform 𝐅. The goal is to output an approximation (in an 𝓁₂ sense) to x̂ in sublinear time. This problem has been well-studied in the special case that 𝐅 is the Discrete Fourier Transform (DFT), and a long line of work has resulted in sparse Fast Fourier Transforms that run in time O(k ⋅ polylog N). However, for transforms 𝐅 other than the DFT (or closely related transforms like the Discrete Cosine Transform), the question is much less settled. In this paper we give sublinear-time algorithms - running in time poly(k log(N)) - for solving the sparse recovery problem for orthogonal transforms 𝐅 that arise from orthogonal polynomials. More precisely, our algorithm works for any 𝐅 that is an orthogonal polynomial transform derived from Jacobi polynomials. The Jacobi polynomials are a large class of classical orthogonal polynomials (and include Chebyshev and Legendre polynomials as special cases), and show up extensively in applications like numerical analysis and signal processing. One caveat of our work is that we require an assumption on the sparsity structure of the sparse vector, although we note that vectors with random support have this property with high probability. Our approach is to give a very general reduction from the k-sparse sparse recovery problem to the 1-sparse sparse recovery problem that holds for any flat orthogonal polynomial transform; then we solve this one-sparse recovery problem for transforms derived from Jacobi polynomials. Frequently, sparse FFT algorithms are described as implementing such a reduction; however, the technical details of such works are quite specific to the Fourier transform and moreover the actual implementations of these algorithms do not use the 1-sparse algorithm as a black box. In this work we give a reduction that works for a broad class of orthogonal polynomial families, and which uses any 1-sparse recovery algorithm as a black box. 

   more » « less
2. Adaptive Machine Unlearning

   Varun Gupta ; Christopher Jung ; Seth Neel ; Aaron Roth ; Saeed Sharifi-Malvajerdi ; Chris Waites ( January 2021 , Neural Information Processing Systems (NeurIPS))

   Data deletion algorithms aim to remove the influence of deleted data points from trained models at a cheaper computational cost than fully retraining those models. However, for sequences of deletions, most prior work in the non-convex setting gives valid guarantees only for sequences that are chosen independently of the models that are published. If people choose to delete their data as a function of the published models (because they don't like what the models reveal about them, for example), then the update sequence is adaptive. In this paper, we give a general reduction from deletion guarantees against adaptive sequences to deletion guarantees against non-adaptive sequences, using differential privacy and its connection to max information. Combined with ideas from prior work which give guarantees for non-adaptive deletion sequences, this leads to extremely flexible algorithms able to handle arbitrary model classes and training methodologies, giving strong provable deletion guarantees for adaptive deletion sequences. We show in theory how prior work for non-convex models fails against adaptive deletion sequences, and use this intuition to design a practical attack against the SISA algorithm of Bourtoule et al. [2021] on CIFAR-10, MNIST, Fashion-MNIST. 

   more » « less
3. AE-OT-GAN: Training GANs from data specific latent distribution

   Dongsheng An, Yang Guo ( January 2020 , European Conference on Computer Vision (ECCV2020))

   Though generative adversarial networks (GANs) are prominent models to generate realistic and crisp images, they are unstable to train and suffer from the mode collapse problem. The problems of GANs come from approximating the intrinsic discontinuous distribution transform map with continuous DNNs. The recently proposed AE-OT model addresses the discontinuity problem by explicitly computing the discontinuous optimal transform map in the latent space of the autoencoder. Though have no mode collapse, the generated images by AE-OT are blurry. In this paper, we propose the AE-OT-GAN model to utilize the advantages of the both models: generate high quality images and at the same time overcome the mode collapse problems. Specifically, we firstly embed the low dimensional image manifold into the latent space by autoencoder (AE). Then the extended semi-discrete optimal transport (SDOT) map is used to generate new latent codes. Finally, our GAN model is trained to generate high quality images from the latent distribution induced by the extended SDOT map. The distribution transform map from this dataset related latent distribution to the data distribution will be continuous, and thus can be well approximated by the continuous DNNs. Additionally, the paired data between the latent codes and the real images gives us further restriction about the generator and stabilizes the training process. Experiments on simple MNIST dataset and complex datasets like CIFAR10 and CelebA show the advantages of the proposed method. 

   more » « less
4. Faster Walsh-Hadamard and Discrete Fourier Transforms from Matrix Non-rigidity

   https://doi.org/10.1145/3564246.3585188  

   Alman, Josh ; Rao, Kevin ( June 2023 , STOC 2023: Proceedings of the 55th Annual ACM Symposium on Theory of Computing)

   We give algorithms with lower arithmetic operation counts for both the Walsh-Hadamard Transform (WHT) and the Discrete Fourier Transform (DFT) on inputs of power-of-2 size N. For the WHT, our new algorithm has an operation count of 23/24N logN + O(N). To our knowledge, this gives the first improvement on the N logN operation count of the simple, folklore Fast Walsh-Hadamard Transform algorithm. For the DFT, our new FFT algorithm uses 15/4N logN + O(N) real arithmetic operations. Our leading constant 15/4 = 3.75 improves on the leading constant of 5 from the Cooley-Tukey algorithm from 1965, leading constant 4 from the split-radix algorithm of Yavne from 1968, leading constant 34/9=3.7777 from a modification of the split-radix algorithm by Van Buskirk from 2004, and leading constant 3.76875 from a theoretically optimized version of Van Buskirk’s algorithm by Sergeev from 2017. Our new WHT algorithm takes advantage of a recent line of work on the non-rigidity of the WHT: we decompose the WHT matrix as the sum of a low-rank matrix and a sparse matrix, and then analyze the structures of these matrices to achieve a lower operation count. Our new DFT algorithm comes from a novel reduction, showing that parts of the previous best FFT algorithms can be replaced by calls to an algorithm for the WHT. Replacing the folklore WHT algorithm with our new improved algorithm leads to our improved FFT. 

   more » « less
5. Radio Frequency Interference Detection and Mitigation Using Compressive Statistical Sensing

   https://doi.org/10.1029/2019RS006902  

   Cucho‐Padin, G. ; Wang, Y. ; Li, E. ; Waldrop, L. ; Tian, Z. ; Kamalabadi, F. ; Perillat, P. ( November 2019 , Radio Science)

   Quasiperiodic radio frequency interference (RFI), such as those generated by telecommunication and active radar systems, is commonly encountered in radio astronomy observations. Such RFI‐contaminated signals contain hidden periodicities due to cyclic features involved in their formation (e.g., carrier frequencies, periodic keying of the amplitude, and baud rates). RFI signal characterization and its subsequent excision based on the well‐known cyclic spectrum analysis have been previously demonstrated; however, the high complexity of the algorithm and the computational cost of its implementation have limited its utility in radio astronomy, rendering less sophisticated solutions. To overcome this challenge, we present a novel method for RFI detection and mitigation based on efficient estimation of the cyclic spectrum by compressive statistical sensing (CSS) of sub‐Nyquist data. CSS performs second‐order statistical estimation such as cyclic spectrum using a reduced number of input samples, thereby enabling accelerated performance. To validate the feasibility of the proposed method, we conduct experiments with simulated data and assess the detection and mitigation results under different parameter settings, for example, interference‐to‐noise ratio, additional RFI sources, frequency resolution, and input data size. We demonstrate the real performance of the method by analyzing radio astronomy data (∼1.3 GHz) acquired with the L‐wide band receiver at the Arecibo Observatory, which is typically corrupted by active air surveillance radars located nearby. Our CSS‐based solution enables robust and efficient detection of the RFI frequency bands present in the L‐band data, and subsequent excision by blanking is also demonstrated.

    

   more » « less