Convex and Nonconvex Optimization Are Both Minimax-Optimal for Noisy Blind Deconvolution Under Random Designs

Yuxin Chen, Jianqing Fan, Bingyan Wang, Yuling Yan

Research output: Contribution to journalArticlepeer-review

Abstract

We investigate the effectiveness of convex relaxation and nonconvex optimization in solving bilinear systems of equations under two different designs (i.e., a sort of random Fourier design and Gaussian design). Despite the wide applicability, the theoretical understanding about these two paradigms remains largely inadequate in the presence of random noise. The current article makes two contributions by demonstrating that (i) a two-stage nonconvex algorithm attains minimax-optimal accuracy within a logarithmic number of iterations, and (ii) convex relaxation also achieves minimax-optimal statistical accuracy vis-à-vis random noise. Both results significantly improve upon the state-of-the-art theoretical guarantees. Supplementary materials for this article are available online.

Original languageEnglish (US)
JournalJournal of the American Statistical Association
DOIs
StateAccepted/In press - 2021

All Science Journal Classification (ASJC) codes

  • Statistics and Probability
  • Statistics, Probability and Uncertainty

Keywords

  • Bilinear systems of equations
  • Blind deconvolution
  • Convex relaxation
  • Leave-one-out analysis
  • Nonconvex optimization

Fingerprint

Dive into the research topics of 'Convex and Nonconvex Optimization Are Both Minimax-Optimal for Noisy Blind Deconvolution Under Random Designs'. Together they form a unique fingerprint.

Cite this