Fast and Global Optimal Nonconvex Matrix Factorization via Perturbed Alternating Proximal Point

Songtao Lu, Mingyi Hong, Zhengdao Wang

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Citation (Scopus)

Abstract

In this paper, we use the perturbed gradient based alternating minimization for solving a class of low-rank matrix factorization problems. Alternating minimization is a simple but popular approach which has been applied to problems in optimization, machine learning, data mining, and signal processing, etc. By leveraging the block structure of the problem, the algorithm updates two blocks of variables in an alternating manner. For the nonconvex optimization problem, it is well-known the alternating minimization algorithm converges to the first-order stationary solution with a global sublinear rate. In this paper, a perturbed alternating proximal point (PA-PP) algorithm is proposed, which 1) minimizes the smooth nonconvex problem by updating two blocks of variables alternatively and 2) adds some random noise occasionally under some conditions to extract the negative curvature of the second-order information of the objective function. We show that the proposed PA-PP is able to converge (with high probability) to the set of second-order stationary solutions (SS2) with a global sublinear rate, and as a consequence quickly finds global optimal solutions for the problems considered.

Original languageEnglish (US)
Title of host publication2019 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2019 - Proceedings
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages2907-2911
Number of pages5
ISBN (Electronic)9781479981311
DOIs
StatePublished - May 2019
Event44th IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2019 - Brighton, United Kingdom
Duration: May 12 2019May 17 2019

Publication series

NameICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings
Volume2019-May
ISSN (Print)1520-6149

Conference

Conference44th IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2019
CountryUnited Kingdom
CityBrighton
Period5/12/195/17/19

Fingerprint

Factorization
Data mining
Learning systems
Signal processing

Keywords

  • Matrix factorization
  • convergence rate
  • first-order stationary (SS1)
  • perturbed alternating proximal point (PA-PP)
  • second-order stationary (SS2)
  • spline function

Cite this

Lu, S., Hong, M., & Wang, Z. (2019). Fast and Global Optimal Nonconvex Matrix Factorization via Perturbed Alternating Proximal Point. In 2019 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2019 - Proceedings (pp. 2907-2911). [8682941] (ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings; Vol. 2019-May). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ICASSP.2019.8682941

Fast and Global Optimal Nonconvex Matrix Factorization via Perturbed Alternating Proximal Point. / Lu, Songtao; Hong, Mingyi; Wang, Zhengdao.

2019 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2019 - Proceedings. Institute of Electrical and Electronics Engineers Inc., 2019. p. 2907-2911 8682941 (ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings; Vol. 2019-May).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Lu, S, Hong, M & Wang, Z 2019, Fast and Global Optimal Nonconvex Matrix Factorization via Perturbed Alternating Proximal Point. in 2019 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2019 - Proceedings., 8682941, ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings, vol. 2019-May, Institute of Electrical and Electronics Engineers Inc., pp. 2907-2911, 44th IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2019, Brighton, United Kingdom, 5/12/19. https://doi.org/10.1109/ICASSP.2019.8682941
Lu S, Hong M, Wang Z. Fast and Global Optimal Nonconvex Matrix Factorization via Perturbed Alternating Proximal Point. In 2019 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2019 - Proceedings. Institute of Electrical and Electronics Engineers Inc. 2019. p. 2907-2911. 8682941. (ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings). https://doi.org/10.1109/ICASSP.2019.8682941
Lu, Songtao ; Hong, Mingyi ; Wang, Zhengdao. / Fast and Global Optimal Nonconvex Matrix Factorization via Perturbed Alternating Proximal Point. 2019 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2019 - Proceedings. Institute of Electrical and Electronics Engineers Inc., 2019. pp. 2907-2911 (ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings).
@inproceedings{9288ab3fffda487ea858b0308132f15a,
title = "Fast and Global Optimal Nonconvex Matrix Factorization via Perturbed Alternating Proximal Point",
abstract = "In this paper, we use the perturbed gradient based alternating minimization for solving a class of low-rank matrix factorization problems. Alternating minimization is a simple but popular approach which has been applied to problems in optimization, machine learning, data mining, and signal processing, etc. By leveraging the block structure of the problem, the algorithm updates two blocks of variables in an alternating manner. For the nonconvex optimization problem, it is well-known the alternating minimization algorithm converges to the first-order stationary solution with a global sublinear rate. In this paper, a perturbed alternating proximal point (PA-PP) algorithm is proposed, which 1) minimizes the smooth nonconvex problem by updating two blocks of variables alternatively and 2) adds some random noise occasionally under some conditions to extract the negative curvature of the second-order information of the objective function. We show that the proposed PA-PP is able to converge (with high probability) to the set of second-order stationary solutions (SS2) with a global sublinear rate, and as a consequence quickly finds global optimal solutions for the problems considered.",
keywords = "Matrix factorization, convergence rate, first-order stationary (SS1), perturbed alternating proximal point (PA-PP), second-order stationary (SS2), spline function",
author = "Songtao Lu and Mingyi Hong and Zhengdao Wang",
year = "2019",
month = "5",
doi = "10.1109/ICASSP.2019.8682941",
language = "English (US)",
series = "ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
pages = "2907--2911",
booktitle = "2019 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2019 - Proceedings",

}

TY - GEN

T1 - Fast and Global Optimal Nonconvex Matrix Factorization via Perturbed Alternating Proximal Point

AU - Lu, Songtao

AU - Hong, Mingyi

AU - Wang, Zhengdao

PY - 2019/5

Y1 - 2019/5

N2 - In this paper, we use the perturbed gradient based alternating minimization for solving a class of low-rank matrix factorization problems. Alternating minimization is a simple but popular approach which has been applied to problems in optimization, machine learning, data mining, and signal processing, etc. By leveraging the block structure of the problem, the algorithm updates two blocks of variables in an alternating manner. For the nonconvex optimization problem, it is well-known the alternating minimization algorithm converges to the first-order stationary solution with a global sublinear rate. In this paper, a perturbed alternating proximal point (PA-PP) algorithm is proposed, which 1) minimizes the smooth nonconvex problem by updating two blocks of variables alternatively and 2) adds some random noise occasionally under some conditions to extract the negative curvature of the second-order information of the objective function. We show that the proposed PA-PP is able to converge (with high probability) to the set of second-order stationary solutions (SS2) with a global sublinear rate, and as a consequence quickly finds global optimal solutions for the problems considered.

AB - In this paper, we use the perturbed gradient based alternating minimization for solving a class of low-rank matrix factorization problems. Alternating minimization is a simple but popular approach which has been applied to problems in optimization, machine learning, data mining, and signal processing, etc. By leveraging the block structure of the problem, the algorithm updates two blocks of variables in an alternating manner. For the nonconvex optimization problem, it is well-known the alternating minimization algorithm converges to the first-order stationary solution with a global sublinear rate. In this paper, a perturbed alternating proximal point (PA-PP) algorithm is proposed, which 1) minimizes the smooth nonconvex problem by updating two blocks of variables alternatively and 2) adds some random noise occasionally under some conditions to extract the negative curvature of the second-order information of the objective function. We show that the proposed PA-PP is able to converge (with high probability) to the set of second-order stationary solutions (SS2) with a global sublinear rate, and as a consequence quickly finds global optimal solutions for the problems considered.

KW - Matrix factorization

KW - convergence rate

KW - first-order stationary (SS1)

KW - perturbed alternating proximal point (PA-PP)

KW - second-order stationary (SS2)

KW - spline function

UR - http://www.scopus.com/inward/record.url?scp=85068999740&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85068999740&partnerID=8YFLogxK

U2 - 10.1109/ICASSP.2019.8682941

DO - 10.1109/ICASSP.2019.8682941

M3 - Conference contribution

AN - SCOPUS:85068999740

T3 - ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings

SP - 2907

EP - 2911

BT - 2019 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2019 - Proceedings

PB - Institute of Electrical and Electronics Engineers Inc.

ER -