Gongguo Tang
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Gongguo Tang has a total of 23 co-authors. Here are the top co-authors by number of shared publications:
- Michael B. Wakin
Department of Electrical Engineering, Colorado School of Mines, Golden, CO, USA
12 shared publications - Qiuwei Li
Department of Electrical Engineering Colorado School of Mines CO USA
6 shared publications - Zhihui Zhu
Department of Computer Science and Engineering, The Ohio State University, Columbus, OH, USA
6 shared publications - Shuang Li
Department of Mathematics University of California Los Angeles
5 shared publications - Dehui Yang
Department of Electrical Engineering Colorado School of Mines
3 shared publications - Arye Nehorai
Preston M. Green Department of Electrical and Systems Engineering, Washington University in St. Louis, St. Louis, USA
2 shared publications
Latest Publications
- 10 June 2022
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Signal Processing
- Vol. 70 (1053587X) , 2985-2999
Landscape Correspondence of Empirical and Population Risks in the Eigendecomposition Problem
Spectral methods include a family of algorithms related to the eigenvectors of certain data-generated matrices. In this work, we are interested in studying the geometric landscape of the eigendecomposition problem in various spectral methods. In particular, we first extend known results regarding the landscape at critical points to larger regions near the critical points in a special case of finding the leading eigenvector of a symmetric matrix. For a more general eigendecomposition problem, inspired by recent findings on the connection between the landscapes of empirical risk and population risk, we then build a novel connection between the landscape of an eigendecomposition problem that uses random measurements and the one that uses the true data matrix. We also apply our theory to a variety of low-rank matrix optimization problems and conduct a series of simulations to illustrate our theoretical findings.
- 10 June 2022
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Signal Processing
- Vol. 70 (1053587X) , 2985-2999
Landscape Correspondence of Empirical and Population Risks in the Eigendecomposition Problem
Spectral methods include a family of algorithms related to the eigenvectors of certain data-generated matrices. In this work, we are interested in studying the geometric landscape of the eigendecomposition problem in various spectral methods. In particular, we first extend known results regarding the landscape at critical points to larger regions near the critical points in a special case of finding the leading eigenvector of a symmetric matrix. For a more general eigendecomposition problem, inspired by recent findings on the connection between the landscapes of empirical risk and population risk, we then build a novel connection between the landscape of an eigendecomposition problem that uses random measurements and the one that uses the true data matrix. We also apply our theory to a variety of low-rank matrix optimization problems and conduct a series of simulations to illustrate our theoretical findings.
- 5 January 2021
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 67 (2) , 1308-1331
The Global Optimization Geometry of Low-Rank Matrix Optimization
This paper considers general rank-constrained optimization problems that minimize a general objective function${f}( {X})$ over the set of rectangular${n}\times {m}$ matrices that have rank at most r. To tackle the rank constraint and also to reduce the computational burden, we factorize$ {X}$ into$ {U} {V} ^{\mathrm {T}}$ where$ {U}$ and$ {V}$ are${n}\times {r}$ and${m}\times {r}$ matrices, respectively, and then optimize over the small matrices$ {U}$ and$ {V}$ . We characterize the global optimization geometry of the nonconvex factored problem and show that the corresponding objective function satisfies the robust strict saddle property as long as the original objective function f satisfies restricted strong convexity and smoothness properties, ensuring global convergence of many local search algorithms (such as noisy gradient descent) in polynomial time for solving the factored problem. We also provide a comprehensive analysis for the optimization geometry of a matrix factorization problem where we aim to find${n}\times {r}$ and${m}\times {r}$ matrices$ {U}$ and$ {V}$ such that$ {U} {V} ^{\mathrm {T}}$ approximates a given matrix$ {X}^\star $ . Aside from the robust strict saddle property, we show that the objective function of the matrix factorization problem has no spurious local minima and obeys the strict saddle property not only for the exact-parameterization case where$\mathrm {rank}( {X}^\star) = {r}$ , but also for the over-parameterization case where$\mathrm {rank}( {X}^\star) < {r}$ and the under-parameterization case where$\mathrm {rank}( {X}^\star) > {r}$ . These geometric properties imply that a number of iterative optimization algorithms (such as gradient descent) converge to a global solution with random initialization.- 5 January 2021
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 67 (2) , 1308-1331
The Global Optimization Geometry of Low-Rank Matrix Optimization
This paper considers general rank-constrained optimization problems that minimize a general objective function${f}( {X})$ over the set of rectangular${n}\times {m}$ matrices that have rank at most r. To tackle the rank constraint and also to reduce the computational burden, we factorize$ {X}$ into$ {U} {V} ^{\mathrm {T}}$ where$ {U}$ and$ {V}$ are${n}\times {r}$ and${m}\times {r}$ matrices, respectively, and then optimize over the small matrices$ {U}$ and$ {V}$ . We characterize the global optimization geometry of the nonconvex factored problem and show that the corresponding objective function satisfies the robust strict saddle property as long as the original objective function f satisfies restricted strong convexity and smoothness properties, ensuring global convergence of many local search algorithms (such as noisy gradient descent) in polynomial time for solving the factored problem. We also provide a comprehensive analysis for the optimization geometry of a matrix factorization problem where we aim to find${n}\times {r}$ and${m}\times {r}$ matrices$ {U}$ and$ {V}$ such that$ {U} {V} ^{\mathrm {T}}$ approximates a given matrix$ {X}^\star $ . Aside from the robust strict saddle property, we show that the objective function of the matrix factorization problem has no spurious local minima and obeys the strict saddle property not only for the exact-parameterization case where$\mathrm {rank}( {X}^\star) = {r}$ , but also for the over-parameterization case where$\mathrm {rank}( {X}^\star) < {r}$ and the under-parameterization case where$\mathrm {rank}( {X}^\star) > {r}$ . These geometric properties imply that a number of iterative optimization algorithms (such as gradient descent) converge to a global solution with random initialization.- 15 July 2020
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Signal Processing Letters
- Vol. 27 (10709908) , 1400-1404
The Global Geometry of Centralized and Distributed Low-rank Matrix Recovery Without Regularization
Low-rank matrix recovery is a fundamental problem in signal processing and machine learning. A recent very popular approach to recovering a low-rank matrix X is to factorize it as a product of two smaller matrices, i.e., X = U V, and then optimize over U, V instead of X. Despite the resulting non-convexity, recent results have shown that many factorized objective functions actually have benign global geometry---with no spurious local minima and satisfying the so-called strict saddle property---ensuring convergence to a global minimum for many local-search algorithms. Such results hold whenever the original objective function is restricted strongly convex and smooth. However, most of these results actually consider a modified cost function that includes a balancing regularizer. While useful for deriving theory, this balancing regularizer does not appear to be necessary in practice. In this work, we close this theory-practice gap by proving that the unaltered factorized non-convex problem, without the balancing regularizer, also has similar benign global geometry. Moreover, we also extend our theoretical results to the field of distributed optimization.
- 15 July 2020
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Signal Processing Letters
- Vol. 27 (10709908) , 1400-1404
The Global Geometry of Centralized and Distributed Low-rank Matrix Recovery Without Regularization
Low-rank matrix recovery is a fundamental problem in signal processing and machine learning. A recent very popular approach to recovering a low-rank matrix X is to factorize it as a product of two smaller matrices, i.e., X = U V, and then optimize over U, V instead of X. Despite the resulting non-convexity, recent results have shown that many factorized objective functions actually have benign global geometry---with no spurious local minima and satisfying the so-called strict saddle property---ensuring convergence to a global minimum for many local-search algorithms. Such results hold whenever the original objective function is restricted strongly convex and smooth. However, most of these results actually consider a modified cost function that includes a balancing regularizer. While useful for deriving theory, this balancing regularizer does not appear to be necessary in practice. In this work, we close this theory-practice gap by proving that the unaltered factorized non-convex problem, without the balancing regularizer, also has similar benign global geometry. Moreover, we also extend our theoretical results to the field of distributed optimization.
- 24 February 2020
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Signal Processing
- Vol. 68 (1053587X) , 1884-1896
Support Recovery for Sparse Signals With Unknown Non-Stationary Modulation
The problem of estimating a sparse signal from low dimensional noisy observations arises in many applications, including super resolution, signal deconvolution, and radar imaging. In this paper, we consider a sparse signal model with nonstationary modulations, in which each dictionary atom contributing to the observations undergoes an unknown, distinct modulation. By applying the lifting technique, under the assumption that the modulating signals live in a common subspace, we recast this sparse recovery and non-stationary blind demodulation problem as the recovery of a column-wise sparse matrix from structured linear observations, and propose to solve it via block L1-norm regularized quadratic minimization. Due to observation noise, the sparse signal and modulation process cannot be recovered exactly. Instead, we aim to recover the sparse support of the ground truth signal and bound the recovery errors of the signal's non-zero components and the modulation process. In particular, we derive sufficient conditions on the sample complexity and regularization parameter for exact support recovery and bound the recovery error on the support. Numerical simulations verify and support our theoretical findings, and we demonstrate the effectiveness of our model in the application of single molecule imaging.
- 24 February 2020
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Signal Processing
- Vol. 68 (1053587X) , 1884-1896
Support Recovery for Sparse Signals With Unknown Non-Stationary Modulation
The problem of estimating a sparse signal from low dimensional noisy observations arises in many applications, including super resolution, signal deconvolution, and radar imaging. In this paper, we consider a sparse signal model with nonstationary modulations, in which each dictionary atom contributing to the observations undergoes an unknown, distinct modulation. By applying the lifting technique, under the assumption that the modulating signals live in a common subspace, we recast this sparse recovery and non-stationary blind demodulation problem as the recovery of a column-wise sparse matrix from structured linear observations, and propose to solve it via block L1-norm regularized quadratic minimization. Due to observation noise, the sparse signal and modulation process cannot be recovered exactly. Instead, we aim to recover the sparse support of the ground truth signal and bound the recovery errors of the signal's non-zero components and the modulation process. In particular, we derive sufficient conditions on the sample complexity and regularization parameter for exact support recovery and bound the recovery error on the support. Numerical simulations verify and support our theoretical findings, and we demonstrate the effectiveness of our model in the application of single molecule imaging.
- 20 November 2019
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 66 (6) , 3893-3913
Atomic Norm Denoising for Complex Exponentials With Unknown Waveform Modulations
Non-stationary blind super-resolution is an extension of the traditional super-resolution problem, which deals with the problem of recovering fine details from coarse measurements. The non-stationary blind super-resolution problem appears in many applications including radar imaging, 3D single-molecule microscopy, computational photography, etc. There is a growing interest in solving non-stationary blind super-resolution task with convex methods due to their robustness to noise and strong theoretical guarantees. Motivated by the recent work on atomic norm minimization in blind inverse problems, we focus here on the signal denoising problem in non-stationary blind superresolution. In particular, we use an atomic norm regularized least-squares problem to denoise a sum of complex exponentials with unknown waveform modulations. We quantify how the mean square error depends on the noise variance and the true signal parameters. Numerical experiments are also implemented to illustrate the theoretical result.
- 20 November 2019
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 66 (6) , 3893-3913
Atomic Norm Denoising for Complex Exponentials With Unknown Waveform Modulations
Non-stationary blind super-resolution is an extension of the traditional super-resolution problem, which deals with the problem of recovering fine details from coarse measurements. The non-stationary blind super-resolution problem appears in many applications including radar imaging, 3D single-molecule microscopy, computational photography, etc. There is a growing interest in solving non-stationary blind super-resolution task with convex methods due to their robustness to noise and strong theoretical guarantees. Motivated by the recent work on atomic norm minimization in blind inverse problems, we focus here on the signal denoising problem in non-stationary blind superresolution. In particular, we use an atomic norm regularized least-squares problem to denoise a sum of complex exponentials with unknown waveform modulations. We quantify how the mean square error depends on the noise variance and the true signal parameters. Numerical experiments are also implemented to illustrate the theoretical result.
- 1 November 2019
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 56, 1217-1221
The Local Geometry of Orthogonal Dictionary Learning using L1 Minimization
Feature learning that extracts concise and general- izable representations for data is one of the central problems in machine learning and signal processing. Sparse dictionary learning, also known as sparse coding, distinguishes from other feature learning techniques in sparsity exploitation, allowing the formulation of nonconvex optimizations that simultaneously uncover a structured dictionary and sparse representations. Despite the popularity of dictionary learning in applications, the landscapes of these optimizations that enable effective learning largely remain a mystery. This work characterizes the local optimization geometry for a simplified version of sparse coding where the L1 norm of the sparse coefficient matrix is minimized subject to orthogonal dictionary constraints. In particular, we show that the ground-truth dictionary and coefficient matrix are locally identifiable under the assumption that the coefficient matrix is sufficiently sparse and the number of training data columns is sufficiently large.
- 1 November 2019
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 56, 1217-1221
The Local Geometry of Orthogonal Dictionary Learning using L1 Minimization
Feature learning that extracts concise and general- izable representations for data is one of the central problems in machine learning and signal processing. Sparse dictionary learning, also known as sparse coding, distinguishes from other feature learning techniques in sparsity exploitation, allowing the formulation of nonconvex optimizations that simultaneously uncover a structured dictionary and sparse representations. Despite the popularity of dictionary learning in applications, the landscapes of these optimizations that enable effective learning largely remain a mystery. This work characterizes the local optimization geometry for a simplified version of sparse coding where the L1 norm of the sparse coefficient matrix is minimized subject to orthogonal dictionary constraints. In particular, we show that the ground-truth dictionary and coefficient matrix are locally identifiable under the assumption that the coefficient matrix is sufficiently sparse and the number of training data columns is sufficiently large.
- 19 August 2019
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Signal Processing
- Vol. 67 (19) , 5184-5199
Simultaneous Sparse Recovery and Blind Demodulation
The task of finding a sparse signal decomposition in an overcomplete dictionary is made more complicated when the signal undergoes an unknown modulation (or convolution in the complementary Fourier domain). Such simultaneous sparse recovery and blind demodulation problems appear in many applications including medical imaging, super resolution, self-calibration, etc. In this paper, we consider a more general sparse recovery and blind demodulation problem in which each atom comprising the signal undergoes a distinct modulation process. Under the assumption that the modulating waveforms live in a known common subspace, we employ the lifting technique and recast this problem as the recovery of a column-wise sparse matrix from structured linear measurements. In this framework, we accomplish sparse recovery and blind demodulation simultaneously by minimizing the induced atomic norm, which in this problem corresponds to the block L1 norm minimization. For perfect recovery in the noiseless case, we derive near optimal sample complexity bounds for Gaussian and random Fourier overcomplete dictionaries. We also provide bounds on recovering the column-wise sparse matrix in the noisy case. Numerical simulations illustrate and support our theoretical results.
- 19 August 2019
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Signal Processing
- Vol. 67 (19) , 5184-5199
Simultaneous Sparse Recovery and Blind Demodulation
The task of finding a sparse signal decomposition in an overcomplete dictionary is made more complicated when the signal undergoes an unknown modulation (or convolution in the complementary Fourier domain). Such simultaneous sparse recovery and blind demodulation problems appear in many applications including medical imaging, super resolution, self-calibration, etc. In this paper, we consider a more general sparse recovery and blind demodulation problem in which each atom comprising the signal undergoes a distinct modulation process. Under the assumption that the modulating waveforms live in a known common subspace, we employ the lifting technique and recast this problem as the recovery of a column-wise sparse matrix from structured linear measurements. In this framework, we accomplish sparse recovery and blind demodulation simultaneously by minimizing the induced atomic norm, which in this problem corresponds to the block L1 norm minimization. For perfect recovery in the noiseless case, we derive near optimal sample complexity bounds for Gaussian and random Fourier overcomplete dictionaries. We also provide bounds on recovering the column-wise sparse matrix in the noisy case. Numerical simulations illustrate and support our theoretical results.
- 31 May 2019
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Control Systems Letters
- Vol. 3 (4) , 942-947
A Convex Relaxation for Model Predictive Control of a Class of Hammerstein Systems
This paper provides conditions under which a structured optimization problem has a convex relaxation. In this optimization problem, the objective function and constraints can be expressed as a function of an optimization variable and a nonlinear function of this variable. A natural application of this optimization problem is model predictive control of a system that has linear dynamics, but for which the input is a non-invertible nonlinear function of an input signal. An example of such a problem is provided in the application of advanced battery management.
- 31 May 2019
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Control Systems Letters
- Vol. 3 (4) , 942-947
A Convex Relaxation for Model Predictive Control of a Class of Hammerstein Systems
This paper provides conditions under which a structured optimization problem has a convex relaxation. In this optimization problem, the objective function and constraints can be expressed as a function of an optimization variable and a nonlinear function of this variable. A natural application of this optimization problem is model predictive control of a system that has linear dynamics, but for which the input is a non-invertible nonlinear function of an input signal. An example of such a problem is provided in the application of advanced battery management.
- Open Access
Provable Bregman-divergence based Methods for Nonconvex and Non-Lipschitz Problems
The (global) Lipschitz smoothness condition is crucial in establishing the convergence theory for most optimization methods. Unfortunately, most machine learning and signal processing problems are not Lipschitz smooth. This motivates us to generalize the concept of Lipschitz smoothness condition to the relative smoothness condition, which is satisfied by any finite-order polynomial objective function. Further, this work develops new Bregman-divergence based algorithms that are guaranteed to converge to a second-order stationary point for any relatively smooth problem. In addition, the proposed optimization methods cover both the proximal alternating minimization and the proximal alternating linearized minimization when we specialize the Bregman divergence to the Euclidian distance. Therefore, this work not only develops guaranteed optimization methods for non-Lipschitz smooth problems but also solves an open problem of showing the second-order convergence guarantees for these alternating minimization methods.
Open AccessProvable Bregman-divergence based Methods for Nonconvex and Non-Lipschitz Problems
The (global) Lipschitz smoothness condition is crucial in establishing the convergence theory for most optimization methods. Unfortunately, most machine learning and signal processing problems are not Lipschitz smooth. This motivates us to generalize the concept of Lipschitz smoothness condition to the relative smoothness condition, which is satisfied by any finite-order polynomial objective function. Further, this work develops new Bregman-divergence based algorithms that are guaranteed to converge to a second-order stationary point for any relatively smooth problem. In addition, the proposed optimization methods cover both the proximal alternating minimization and the proximal alternating linearized minimization when we specialize the Bregman divergence to the Euclidian distance. Therefore, this work not only develops guaranteed optimization methods for non-Lipschitz smooth problems but also solves an open problem of showing the second-order convergence guarantees for these alternating minimization methods.
- Open Access
Approximate Support Recovery of Atomic Line Spectral Estimation: A Tale of Resolution and Precision
This work investigates the parameter estimation performance of super-resolution line spectral estimation using atomic norm minimization. The focus is on analyzing the algorithm's accuracy of inferring the frequencies and complex magnitudes from noisy observations. When the Signal-to-Noise Ratio is reasonably high and the true frequencies are separated by $O(\frac{1}{n})$, the atomic norm estimator is shown to localize the correct number of frequencies, each within a neighborhood of size $O(\sqrt{{\log n}/{n^3}} \sigma)$ of one of the true frequencies. Here $n$ is half the number of temporal samples and $\sigma^2$ is the Gaussian noise variance. The analysis is based on a primal-dual witness construction procedure. The obtained error bound matches the Cram\'er-Rao lower bound up to a logarithmic factor. The relationship between resolution (separation of frequencies) and precision or accuracy of the estimator is highlighted. Our analysis also reveals that the atomic norm minimization can be viewed as a convex way to solve a $\ell_1$-norm regularized, nonlinear and nonconvex least-squares problem to global optimality.Open AccessApproximate Support Recovery of Atomic Line Spectral Estimation: A Tale of Resolution and Precision
This work investigates the parameter estimation performance of super-resolution line spectral estimation using atomic norm minimization. The focus is on analyzing the algorithm's accuracy of inferring the frequencies and complex magnitudes from noisy observations. When the Signal-to-Noise Ratio is reasonably high and the true frequencies are separated by $O(\frac{1}{n})$, the atomic norm estimator is shown to localize the correct number of frequencies, each within a neighborhood of size $O(\sqrt{{\log n}/{n^3}} \sigma)$ of one of the true frequencies. Here $n$ is half the number of temporal samples and $\sigma^2$ is the Gaussian noise variance. The analysis is based on a primal-dual witness construction procedure. The obtained error bound matches the Cram\'er-Rao lower bound up to a logarithmic factor. The relationship between resolution (separation of frequencies) and precision or accuracy of the estimator is highlighted. Our analysis also reveals that the atomic norm minimization can be viewed as a convex way to solve a $\ell_1$-norm regularized, nonlinear and nonconvex least-squares problem to global optimality.