American Institute of Mathematical Sciences

Advanced
  • Previous Article
    Indirect methods for fuel-minimal rendezvous with a large population of temporarily captured orbiters
  • NACO Home
  • This Issue
  • Next Article
    Application of robust optimization for a product portfolio problem using an invasive weed optimization algorithm
June  2019, 9(2): 211-224. doi: 10.3934/naco.2019015

Homotopy method for matrix rank minimization based on the matrix hard thresholding method

Zhengshan Dong 1,2, , Jianli Chen 2, and  Wenxing Zhu 2,,

1. 

Ruijie Networks Co., Ltd, Fuzhou 350108, China
2. 

Center for Discrete Mathematics and Theoretical Computer Science, Fuzhou University, Fuzhou 350108, China

* Corresponding author: wxzhu@fzu.edu.cn

Received  May 2018 Revised  August 2018 Published  January 2019

Fund Project: This research is supported by the National Natural Science Foundation of China under Grant 61672005.

Based on the matrix hard thresholding method, a homotopy method is proposed for solving the matrix rank minimization problem. This method iteratively solves a series of regularization subproblems, whose solutions are given in closed form by the matrix hard thresholding operator. Under some mild assumptions, convergence of the proposed method is proved. The proposed method does not depend on a prior knowledge of exact rank value. Numerical experiments demonstrate that the proposed homotopy method weakens the affection of the choice of the regularization parameter, and is more efficient and effective than the existing sate-of-the-art methods.

Keywords: matrix rank minimization, matrix completion, iterative hard thresholding method, hard thresholding operator, homotopy method.
Mathematics Subject Classification: Primary: 15A29, 65F10, 90C27.
Citation: Zhengshan Dong, Jianli Chen, Wenxing Zhu. Homotopy method for matrix rank minimization based on the matrix hard thresholding method. Numerical Algebra, Control & Optimization, 2019, 9 (2) : 211-224. doi: 10.3934/naco.2019015
References:
[1]

J. D. Blanchard, J. Tanner and K. Wei, CGIHT: Conjugate gradient iterative hard thresholding for compressed sensing and matrix completion, Information and Inference: A Journal of the IMA, 4 (2014), 289-327.  doi: 10.1093/imaiai/iav011.  Google Scholar

[2]

T. Blumensath and M. E. Davies, Iterative thresholding for sparse approximations, Journal of Constructive Approximation, 14 (2008), 629-654.  doi: 10.1007/s00041-008-9035-z.  Google Scholar

[3]

T. Blumensath and M. E. Davies, Normalised itertive hard thresholding: guaranteed stability and performance, IEEE Journal of Selected Topics in Signal Processing, 4 (2010), 298-309.   Google Scholar

[4]

E. J. Candès and B. Recht, Exact matrix completion via convex optimization, Foundations of Computational Mathematics, 9 (2009), 717-772.  doi: 10.1007/s10208-009-9045-5.  Google Scholar

[5]

E. J. Candès and T. Tao, The power of convex relaxation: Near-optimal matrix completion, IEEE Transactions on Information Theory, 56 (2009), 2053-1080.  doi: 10.1109/TIT.2010.2044061.  Google Scholar

[6]

M. Fazel, H. Hindi and S. Boyd, Rank minimization and applications in system theory, Proceedings of the American Control Conference, 4 (2004), 3273-3278.   Google Scholar

[7]

M. Fazel, T. K. Pong, D. Sun and P. Tseng, Hankel matrix rank minimization with applications to system identification and realization, SIAM Journal on Matrix Analysis and Applications, 34 (2013), 946-977.  doi: 10.1137/110853996.  Google Scholar

[8]

D. Goldfarb and S. Ma, Convergence of fixed-point continuation algorithms for matrix rank minimization, Foundations of Computational Mathematics, 11 (2011), 183-210.  doi: 10.1007/s10208-011-9084-6.  Google Scholar

[9]

J. P. Haldar and D. Hernando, Rank-constrained solutions to linear matrix equations using powerfactorization, IEEE Signal Processing Letters, 16 (2009), 584-587.   Google Scholar

[10]

N. J. A. Harvey, D. R. Karger and S. Yekhanin, The complexity of matrix completion, Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithm, (2006), 1103–1111. doi: 10.1145/1109557.1109679.  Google Scholar

[11]

A. Kyrillidis and V. Cevher, Martix ALPS: Accelerated low rank and sparse matrix reconstruction, Technical Report, 2012. Google Scholar

[12]

A. Kyrillidis and V. Cevher, Martix recips for hard thresholding methods, Journal of Mathematical Imaging and Vision, 48 (2014), 235-265.  doi: 10.1007/s10851-013-0434-7.  Google Scholar

[13]

Y. Liu, J. Tao, H. Zhang, X. Xiu and L. Kong, Fused LASSO penalized least absolute deviation estimator for high dimensional linear regression, Numerical Algebra, Control & Optimization, 8 (2018), 97–117. doi: 10.3934/naco.2018006.  Google Scholar

[14]

Z. Liu and L. Vandenberghe, Interior-point method for nuclear norm approximation with application to system identification, SIAM Journal on Matrix Analysis and Applications, 31 (2009), 1235-1256.  doi: 10.1137/090755436.  Google Scholar

[15]

C. Lu, J. Tang, S. Yan and Z. Lin, Generalized nonconvex nonsmooth low-rank minimization, IEEE Conference on Computer Vision and Pattern Recognition, 2014. Google Scholar

[16]

Z. Lu, Iterative hard thresholding methods for $l_0$ regularized convex cone programming, Mathematical Programming, 147 (2014), 125-154.  doi: 10.1007/s10107-013-0714-4.  Google Scholar

[17]

Z. Lu and Y. Zhang, Penalty decomposition methods for rank minimization, Optimization Methods and Software, 30 (2015), 531-558.  doi: 10.1080/10556788.2014.936438.  Google Scholar

[18]

S. Ma, D. Goldfarb and L. Chen, Fixed point and bregman iterative methods for matrix rank minimization, Mathematical Programming, 128 (2011), 321-353.  doi: 10.1007/s10107-009-0306-5.  Google Scholar

[19]

K. Mohan and M. Fazel, Reweighted nuclear norm minimization with application to system identification, Proceedings of the American Control Conference, 2010. Google Scholar

[20]

K. Mohan and M. Fazel, Iterative reweighted algorithms for matrix rank minimization, Journal of Machine Learning Research, 13 (2012), 3441-3473.   Google Scholar

[21]

B. Recht, M. Fazel and P. A. Parrilo, Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization, SIAM Review, 52 (2010), 471-501.  doi: 10.1137/070697835.  Google Scholar

[22]

J. Tanner and K. Wei, Normalized iterative hard thresholding for matrix completion, SIAM Journal on Scientific Computing, 35 (2013), S104–S125. doi: 10.1137/120876459.  Google Scholar

[23]

Z. Wen, W. Yin and Y. Zhang, Solving a low-rank factorization model for matrix completion by a non-linear successive over-relaxation algorithm, Mathematical Programming Computation, 4 (2012), 333-361.  doi: 10.1007/s12532-012-0044-1.  Google Scholar

[24]

Z. Weng and X. Wang, Low-rank matrix completion for array signal processing, IEEE International Conference on Speech and Signal Processing, (2012), 2697–2700. Google Scholar

show all references

References:
[1]

J. D. Blanchard, J. Tanner and K. Wei, CGIHT: Conjugate gradient iterative hard thresholding for compressed sensing and matrix completion, Information and Inference: A Journal of the IMA, 4 (2014), 289-327.  doi: 10.1093/imaiai/iav011.  Google Scholar

[2]

T. Blumensath and M. E. Davies, Iterative thresholding for sparse approximations, Journal of Constructive Approximation, 14 (2008), 629-654.  doi: 10.1007/s00041-008-9035-z.  Google Scholar

[3]

T. Blumensath and M. E. Davies, Normalised itertive hard thresholding: guaranteed stability and performance, IEEE Journal of Selected Topics in Signal Processing, 4 (2010), 298-309.   Google Scholar

[4]

E. J. Candès and B. Recht, Exact matrix completion via convex optimization, Foundations of Computational Mathematics, 9 (2009), 717-772.  doi: 10.1007/s10208-009-9045-5.  Google Scholar

[5]

E. J. Candès and T. Tao, The power of convex relaxation: Near-optimal matrix completion, IEEE Transactions on Information Theory, 56 (2009), 2053-1080.  doi: 10.1109/TIT.2010.2044061.  Google Scholar

[6]

M. Fazel, H. Hindi and S. Boyd, Rank minimization and applications in system theory, Proceedings of the American Control Conference, 4 (2004), 3273-3278.   Google Scholar

[7]

M. Fazel, T. K. Pong, D. Sun and P. Tseng, Hankel matrix rank minimization with applications to system identification and realization, SIAM Journal on Matrix Analysis and Applications, 34 (2013), 946-977.  doi: 10.1137/110853996.  Google Scholar

[8]

D. Goldfarb and S. Ma, Convergence of fixed-point continuation algorithms for matrix rank minimization, Foundations of Computational Mathematics, 11 (2011), 183-210.  doi: 10.1007/s10208-011-9084-6.  Google Scholar

[9]

J. P. Haldar and D. Hernando, Rank-constrained solutions to linear matrix equations using powerfactorization, IEEE Signal Processing Letters, 16 (2009), 584-587.   Google Scholar

[10]

N. J. A. Harvey, D. R. Karger and S. Yekhanin, The complexity of matrix completion, Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithm, (2006), 1103–1111. doi: 10.1145/1109557.1109679.  Google Scholar

[11]

A. Kyrillidis and V. Cevher, Martix ALPS: Accelerated low rank and sparse matrix reconstruction, Technical Report, 2012. Google Scholar

[12]

A. Kyrillidis and V. Cevher, Martix recips for hard thresholding methods, Journal of Mathematical Imaging and Vision, 48 (2014), 235-265.  doi: 10.1007/s10851-013-0434-7.  Google Scholar

[13]

Y. Liu, J. Tao, H. Zhang, X. Xiu and L. Kong, Fused LASSO penalized least absolute deviation estimator for high dimensional linear regression, Numerical Algebra, Control & Optimization, 8 (2018), 97–117. doi: 10.3934/naco.2018006.  Google Scholar

[14]

Z. Liu and L. Vandenberghe, Interior-point method for nuclear norm approximation with application to system identification, SIAM Journal on Matrix Analysis and Applications, 31 (2009), 1235-1256.  doi: 10.1137/090755436.  Google Scholar

[15]

C. Lu, J. Tang, S. Yan and Z. Lin, Generalized nonconvex nonsmooth low-rank minimization, IEEE Conference on Computer Vision and Pattern Recognition, 2014. Google Scholar

[16]

Z. Lu, Iterative hard thresholding methods for $l_0$ regularized convex cone programming, Mathematical Programming, 147 (2014), 125-154.  doi: 10.1007/s10107-013-0714-4.  Google Scholar

[17]

Z. Lu and Y. Zhang, Penalty decomposition methods for rank minimization, Optimization Methods and Software, 30 (2015), 531-558.  doi: 10.1080/10556788.2014.936438.  Google Scholar

[18]

S. Ma, D. Goldfarb and L. Chen, Fixed point and bregman iterative methods for matrix rank minimization, Mathematical Programming, 128 (2011), 321-353.  doi: 10.1007/s10107-009-0306-5.  Google Scholar

[19]

K. Mohan and M. Fazel, Reweighted nuclear norm minimization with application to system identification, Proceedings of the American Control Conference, 2010. Google Scholar

[20]

K. Mohan and M. Fazel, Iterative reweighted algorithms for matrix rank minimization, Journal of Machine Learning Research, 13 (2012), 3441-3473.   Google Scholar

[21]

B. Recht, M. Fazel and P. A. Parrilo, Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization, SIAM Review, 52 (2010), 471-501.  doi: 10.1137/070697835.  Google Scholar

[22]

J. Tanner and K. Wei, Normalized iterative hard thresholding for matrix completion, SIAM Journal on Scientific Computing, 35 (2013), S104–S125. doi: 10.1137/120876459.  Google Scholar

[23]

Z. Wen, W. Yin and Y. Zhang, Solving a low-rank factorization model for matrix completion by a non-linear successive over-relaxation algorithm, Mathematical Programming Computation, 4 (2012), 333-361.  doi: 10.1007/s12532-012-0044-1.  Google Scholar

[24]

Z. Weng and X. Wang, Low-rank matrix completion for array signal processing, IEEE International Conference on Speech and Signal Processing, (2012), 2697–2700. Google Scholar

Table 4.  Numerical results on random uniform matrices with size $ m = n = 500 $ and sampling ratio $ \tau = 0.5. $
r=5 r=10
Alg. NS time rank rel.err. NS time rank rel.err.
FPCA 50 6.71 5 9.22E-06 50 13.61 10 2.66E-05
PD 50 24.08 5 7.70E-05 50 33.65 10 8.96E-05
HIHT 50 19.37 5 5.33E-05 50 16.12 10 4.78E-05
r=30 r=50
Alg. NS time rank rel.err. NS time rank rel.err.
FPCA 0 43.74 16.6 3.80E-02 - - - -
PD 50 39.55 30 7.42E-05 50 53.83 50 1.00E-04
HIHT 50 36.34 30 3.52E-05 50 47.36 50 9.93E-06
r=70 r=90
Alg. NS time rank rel.err. NS time rank rel.err.
FPCA - - - - - - - -
PD 50 87.17 70 1.51E-04 50 294.05 90 2.38E-04
HIHT 50 70.3 70 6.31E-05 50 82.79 90 2.02E-04
Table Options

Download as excel

r=5 r=10
Alg. NS time rank rel.err. NS time rank rel.err.
FPCA 50 6.71 5 9.22E-06 50 13.61 10 2.66E-05
PD 50 24.08 5 7.70E-05 50 33.65 10 8.96E-05
HIHT 50 19.37 5 5.33E-05 50 16.12 10 4.78E-05
r=30 r=50
Alg. NS time rank rel.err. NS time rank rel.err.
FPCA 0 43.74 16.6 3.80E-02 - - - -
PD 50 39.55 30 7.42E-05 50 53.83 50 1.00E-04
HIHT 50 36.34 30 3.52E-05 50 47.36 50 9.93E-06
r=70 r=90
Alg. NS time rank rel.err. NS time rank rel.err.
FPCA - - - - - - - -
PD 50 87.17 70 1.51E-04 50 294.05 90 2.38E-04
HIHT 50 70.3 70 6.31E-05 50 82.79 90 2.02E-04
Table 1.  Influence of the regularization parameter $ \lambda $
$ \eta $ IHT HIHT
NS time rank rel.err. NS time rank rel.err.
50 4 122.43 38.56 1.29E-01 50 35.33 40 1.17E-05
20 50 18.83 40.00 5.82E-05 50 19.86 40 1.17E-05
10 47 23.69 40.06 2.52E-03 50 23.25 40 1.38E-05
5 0 52.92 227.10 6.33E-01 0 45.41 227.72 6.34E-01
Table Options

Download as excel

$ \eta $ IHT HIHT
NS time rank rel.err. NS time rank rel.err.
50 4 122.43 38.56 1.29E-01 50 35.33 40 1.17E-05
20 50 18.83 40.00 5.82E-05 50 19.86 40 1.17E-05
10 47 23.69 40.06 2.52E-03 50 23.25 40 1.38E-05
5 0 52.92 227.10 6.33E-01 0 45.41 227.72 6.34E-01
Table 2.  Influence of maximum number of inner iterations on Algorithm 2
HIHT
$ step $ NS time rank rel.err.
5 50 16.72 40 4.35E-05
10 50 18.13 40 2.09E-05
20 50 18.97 40 1.35E-05
30 50 19.29 40 1.16E-05
40 50 19.27 40 1.16E-05
50 50 19.24 40 1.17E-05
60 50 19.72 40 1.01E-05
70 50 19.71 40 1.02E-05
Table Options

Download as excel

HIHT
$ step $ NS time rank rel.err.
5 50 16.72 40 4.35E-05
10 50 18.13 40 2.09E-05
20 50 18.97 40 1.35E-05
30 50 19.29 40 1.16E-05
40 50 19.27 40 1.16E-05
50 50 19.24 40 1.17E-05
60 50 19.72 40 1.01E-05
70 50 19.71 40 1.02E-05
Table 3.  Numerical results on random Gaussian matrices with size $ m = n = 500 $ and sampling ratio $ \tau = 0.5 $
r=5 r=10
Alg. NS time rank rel.err. NS time rank rel.err.
FPCA 50 4.69 5 1.24E-06 50 5.19 10 2.90E-06
PD 50 95.92 5 5.92E-05 50 102.83 10 8.54E-05
HIHT 50 10.91 5 7.49E-05 50 12.54 10 7.02E-05
r=30 r=50
Alg. NS time rank rel.err. NS time rank rel.err.
FPCA 50 5.78 30 1.44E-05 50 255.32 50 1.61E-04
PD 50 102.38 30 9.40E-05 50 106.19 50 1.50E-04
HIHT 50 18.57 30 6.63E-05 50 24.13 50 2.67E-05
r=70 r=90
Alg. NS time rank rel.err. NS time rank rel.err.
FPCA 50 279.55 70 2.23E-04 50 332.90 90 2.71E-04
PD 50 164.06 70 1.78E-04 50 471.48 90 2.51E-04
HIHT 50 38.23 70 5.01E-05 50 84.32 90 2.08E-04
Table Options

Download as excel

r=5 r=10
Alg. NS time rank rel.err. NS time rank rel.err.
FPCA 50 4.69 5 1.24E-06 50 5.19 10 2.90E-06
PD 50 95.92 5 5.92E-05 50 102.83 10 8.54E-05
HIHT 50 10.91 5 7.49E-05 50 12.54 10 7.02E-05
r=30 r=50
Alg. NS time rank rel.err. NS time rank rel.err.
FPCA 50 5.78 30 1.44E-05 50 255.32 50 1.61E-04
PD 50 102.38 30 9.40E-05 50 106.19 50 1.50E-04
HIHT 50 18.57 30 6.63E-05 50 24.13 50 2.67E-05
r=70 r=90
Alg. NS time rank rel.err. NS time rank rel.err.
FPCA 50 279.55 70 2.23E-04 50 332.90 90 2.71E-04
PD 50 164.06 70 1.78E-04 50 471.48 90 2.51E-04
HIHT 50 38.23 70 5.01E-05 50 84.32 90 2.08E-04
Table 5.  Computational results on random Gaussian (or uniform) matrices with size $ m = n = 4000 $, $ r = 200 $, and sampling ratio $ \tau = 0.3. $
Gaussian matrix uniform matrix
Alg. NS time rank rel.err. NS time rank rel.err.
FPCA 50 284.36 200 8.28E-05 0 1887.44 1.06 2.35E-02
PD 50 13232.85 200 1.02E-04 50 5976.50 200 9.89E-05
HIHT 50 4427.63 200 1.63E-05 50 7637.74 200 1.70E-05
Table Options

Download as excel

Gaussian matrix uniform matrix
Alg. NS time rank rel.err. NS time rank rel.err.
FPCA 50 284.36 200 8.28E-05 0 1887.44 1.06 2.35E-02
PD 50 13232.85 200 1.02E-04 50 5976.50 200 9.89E-05
HIHT 50 4427.63 200 1.63E-05 50 7637.74 200 1.70E-05
[1]

Dan Zhu, Rosemary A. Renaut, Hongwei Li, Tianyou Liu. Fast non-convex low-rank matrix decomposition for separation of potential field data using minimal memory. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020076
[2]

Sihem Guerarra. Maximum and minimum ranks and inertias of the Hermitian parts of the least rank solution of the matrix equation AXB = C. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 75-86. doi: 10.3934/naco.2020016
[3]

Marion Darbas, Jérémy Heleine, Stephanie Lohrengel. Numerical resolution by the quasi-reversibility method of a data completion problem for Maxwell's equations. Inverse Problems & Imaging, 2020, 14 (6) : 1107-1133. doi: 10.3934/ipi.2020056
[4]

Peizhao Yu, Guoshan Zhang, Yi Zhang. Decoupling of cubic polynomial matrix systems. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 13-26. doi: 10.3934/naco.2020012
[5]

Shengxin Zhu, Tongxiang Gu, Xingping Liu. AIMS: Average information matrix splitting. Mathematical Foundations of Computing, 2020, 3 (4) : 301-308. doi: 10.3934/mfc.2020012
[6]

Mehdi Bastani, Davod Khojasteh Salkuyeh. On the GSOR iteration method for image restoration. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 27-43. doi: 10.3934/naco.2020013
[7]

Parikshit Upadhyaya, Elias Jarlebring, Emanuel H. Rubensson. A density matrix approach to the convergence of the self-consistent field iteration. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 99-115. doi: 10.3934/naco.2020018
[8]

Hong Niu, Zhijiang Feng, Qijin Xiao, Yajun Zhang. A PID control method based on optimal control strategy. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 117-126. doi: 10.3934/naco.2020019
[9]

Li-Bin Liu, Ying Liang, Jian Zhang, Xiaobing Bao. A robust adaptive grid method for singularly perturbed Burger-Huxley equations. Electronic Research Archive, 2020, 28 (4) : 1439-1457. doi: 10.3934/era.2020076
[10]

Zexuan Liu, Zhiyuan Sun, Jerry Zhijian Yang. A numerical study of superconvergence of the discontinuous Galerkin method by patch reconstruction. Electronic Research Archive, 2020, 28 (4) : 1487-1501. doi: 10.3934/era.2020078
[11]

Yuxia Guo, Shaolong Peng. A direct method of moving planes for fully nonlinear nonlocal operators and applications. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020462
[12]

Noah Stevenson, Ian Tice. A truncated real interpolation method and characterizations of screened Sobolev spaces. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5509-5566. doi: 10.3934/cpaa.2020250
[13]

Yue Feng, Yujie Liu, Ruishu Wang, Shangyou Zhang. A conforming discontinuous Galerkin finite element method on rectangular partitions. Electronic Research Archive, , () : -. doi: 10.3934/era.2020120
[14]

S. Sadeghi, H. Jafari, S. Nemati. Solving fractional Advection-diffusion equation using Genocchi operational matrix based on Atangana-Baleanu derivative. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020435
[15]

Yuri Fedorov, Božidar Jovanović. Continuous and discrete Neumann systems on Stiefel varieties as matrix generalizations of the Jacobi–Mumford systems. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020375
[16]

Leilei Wei, Yinnian He. A fully discrete local discontinuous Galerkin method with the generalized numerical flux to solve the tempered fractional reaction-diffusion equation. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020319
[17]

Gang Bao, Mingming Zhang, Bin Hu, Peijun Li. An adaptive finite element DtN method for the three-dimensional acoustic scattering problem. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020351
[18]

Zuliang Lu, Fei Huang, Xiankui Wu, Lin Li, Shang Liu. Convergence and quasi-optimality of $ L^2- $norms based an adaptive finite element method for nonlinear optimal control problems. Electronic Research Archive, 2020, 28 (4) : 1459-1486. doi: 10.3934/era.2020077
[19]

Mostafa Mbekhta. Representation and approximation of the polar factor of an operator on a Hilbert space. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020463
[20]

Kha Van Huynh, Barbara Kaltenbacher. Some application examples of minimization based formulations of inverse problems and their regularization. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020074

 Impact Factor: 

Tools

Metrics

  • PDF downloads (100)
  • HTML views (558)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2020 American Institute of Mathematical Sciences