Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Low rank and sparse decomposition based on extended \({LL}_{p}\) norm

  • Published:
Multimedia Tools and Applications Aims and scope Submit manuscript

Abstract

The problem of decomposing a given matrix into its low-rank and sparse components, known as robust principle component analysis (RPCA), has found many applications in variety of fields. In this problem, the goal is to recover the two components through constrained minimization of a combination of the rank function and \({l}_{0}\) norm. Oftentimes, exact recovery of the low-rank component is desired. Since the problem is NP-Hard, a convex relaxation where nuclear norm and \({l}_{1}\) norm are utilized to induce low-rank and sparsity is used. However, it may obtain suboptimal results since the nuclear norm cannot well approximate the rank function. This paper addresses the low-rank and sparse decomposition (LRSD) problem by utilizing a new nonconvex approximation function for the rank. In our LRSD approach, the nonconvex \({LL}_{p}\) norm is extended on singular values to obtain a new surrogate, called \({eLL}_{p}\), for the rank function. To solve the associated minimization problem, an efficient algorithm based on alternating direction multiplier method (ADMM) and Majorization-Minimization (MM) algorithm is developed. To verify the effectiveness of the proposed method, it is applied to the synthetic data and real applications including face image shadow removal and image denoising. Experimental results show the effectiveness of the proposed method compared with the other methods in terms of the recovery errors and objective evaluations. In real applications of the images, our proposed method achieves higher recovery accuracy in a less time.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9

Similar content being viewed by others

Data availability

Data sharing not applicable to this article as no datasets were generated or analysed during the current study.

Notes

  1. http://vision.ucsd.edu/~leekc/ExtYaleDatabase/Yale%20Face%20Database.htm

References

  1. Shang, F, Liu, Y, Tong, H, Cheng, J, Cheng, H (2014) Structured Low-Rank Matrix Factorization with Missing and Grossly Corrupted Observations. arXiv:1409.1062. Accessed 10 Apr 2022

  2. Hotelling H (1933) Analysis of a complex of statistical variables into principal components. J Educat Psych 24:417–441

    Article  Google Scholar 

  3. Wold S, Esbensen K, Geladi P (1987) Principal component analysis. Chemom Intell Lab Syst 2(1):37–52

    Article  CAS  Google Scholar 

  4. Liu G, Lin Z, Yan S, Sun J, Yu Y, Ma Y (2013) Robust Recovery of Subspace Structures by Low-Rank Representation. In IEEE Trans Pattern Anal Mach Intell 35(1):171–184

    Article  Google Scholar 

  5. Lin, Z, Chen, M, Ma, Y (2010) The Augmented Lagrange Multiplier Method for Exact Recovery Of Corrupted Low-Rank Matrices. arXiv preprint arXiv:1009.5055. Accessed 10 Apr 2022

  6. Wright J, Ganesh A, Rao S, Peng Y, Ma Y (2009) Robust principal component analysis: exact recovery of corrupted low-rank matrices via convex optimization. Advances in neural information processing systems, p 22

  7. Liu G, Lin Z, Yu Y (2010) Robust subspace segmentation by Low-Rank Representation. In Proceedings of the 27th International Conference on Machine Learning (ICML-10), pp 663–670

  8. Chen CF, Wei CP, Wang YCF (2012) Low-rank matrix recovery with structural incoherence for robust face recognition. In 2012 IEEE conference on computer vision and pattern recognition, Jun 16, pp 2618–2625

  9. Wei CP, Chen CF, Wang YCF (2014) Robust face recognition with structurally incoherent low-rank matrix decomposition. IEEE Trans Image Process 23(8):3294–3307

    Article  MathSciNet  PubMed  Google Scholar 

  10. Hui KF, Shen XJ, Abhadiomhen SE, Zhan YZ (2022) Robust low-rank representation via residual projection for image classification. Knowl-Based Syst 241:108230

    Article  Google Scholar 

  11. Wang ZY, Abhadiomhen SE, Liu ZF, Shen XJ, Gao WY, Li SY (2021) Multi-view intrinsic low-rank representation for robust face recognition and clustering. IET Image Proc 15(14):3573–3584

    Article  Google Scholar 

  12. Liu X, Zhao G, Yao J, Qi C (2015) Background subtraction based on low-rank and structured sparse decomposition. IEEE Trans Image Process 24(8):2502–2514

    Article  ADS  MathSciNet  Google Scholar 

  13. Xue Y, Guo X, Cao X (2012) Motion saliency detection using low-rank and sparse decomposition. In 2012 IEEE international conference on acoustics, speech and signal processing (ICASSP), Mar 25, pp 1485–1488

  14. Yang Z, Fan L, Yang Y, Yang Z, Gui G (2020) Generalized nuclear norm and Laplacian scale mixture based low-rank and sparse decomposition for video foreground-background separation. Signal Process 172:107527

    Article  Google Scholar 

  15. Zhang Q, Lu W, Yang X (2021) A Novel Low-Rank and Sparse Decomposition Model and Its Application in Moving Objects Detection. Autom Control Comput Sci 55(4):388–395

    Article  Google Scholar 

  16. Min K, Zhang Z, Wright J, Ma Y (2010) Decomposing background topics from keywords by principal component pursuit. In Proceedings of the 19th ACM international conference on Information and knowledge management, Oct 26, pp 269–278

  17. Zhao ZL, Huang L, Wang CD, Lai JH, Yu PS (2017) Low-rank and sparse matrix completion for recommendation (vol 10638). International conference on neural information processing (ICONIP 2017), lecture notes in computer science, pp 3–13

  18. Nagarajaiah S (2017) Sparse and low-rank methods in structural system identification and monitoring. Procedia Eng 199:62–69

    Article  Google Scholar 

  19. Zhang C, Liu J, Tian Q, Xu C, Lu H, Ma S (2011) Image classification by non-negative sparse coding, low-rank and sparse decomposition. In CVPR 2011:1673–1680

    Google Scholar 

  20. Zhang C, Liu J, Liang C, Xue Z, Pang J, Huang Q (2014) Image classification by non-negative sparse coding, correlation constrained low-rank and sparse decomposition. Comput Vis Image Underst 123:14–22

    Article  Google Scholar 

  21. Li, Y. and Wang, P., 2016. Robust image hashing based on low-rank and sparse decomposition. In 2016 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 2154–2158.

  22. Xie T, Li S, Sun B (2019) Hyperspectral images denoising via nonconvex regularized low-rank and sparse matrix decomposition. IEEE Trans Image Process 29:44–56

    Article  ADS  MathSciNet  PubMed  Google Scholar 

  23. Du J, Huang H, Jing XJ, Chen X (2016) Cyclostationary feature based spectrum sensing via low-rank and sparse decomposition in cognitive radio networks. In 2016 16th international symposium on communications and information technologies (ISCIT), Qingdao, China, Sept 26, pp 615–619

  24. Yu S, Yiquan W (2018) Subspace clustering based on latent low rank representation with Frobenius norm minimization. Neurocomput 275:2479–2489

    Article  Google Scholar 

  25. Abhadiomhen SE, Wang Z, Shen X, Fan J (2021) Multiview common subspace clustering via coupled low rank representation. ACM Trans Intell Syst Technol (TIST) 12(4):1–25

    Article  Google Scholar 

  26. Abhadiomhen SE, Wang Z, Shen X (2022) Coupled low rank representation and subspace clustering. Appl Intell 52(1):530–546

    Article  Google Scholar 

  27. Shi C, Cheng Y, Wang J, Wang Y, Mori K, Tamura S (2017) Low-rank and sparse decomposition based shape model and probabilistic atlas for automatic pathological organ segmentation. Med Image Anal 38:30–49

    Article  PubMed  Google Scholar 

  28. Candès EJ, Li X, Ma Y, Wright J (2011) Robust principal component analysis? J ACM (JACM) 58(3):1–37

    Article  MathSciNet  Google Scholar 

  29. Goldfarb D, Ma S, Scheinberg K (2013) Fast alternating linearization methods for minimizing the sum of two convex functions. Math Program 141(1):349–382

    Article  MathSciNet  Google Scholar 

  30. Tang G, Nehorai A (2011) Robust principal component analysis based on low-rank and block-sparse matrix decomposition. In 2011 45th annual conference on information sciences and systems, Baltimore, MD, Mar 23, pp 1–5

  31. Candes EJ, Recht B (2009) Exact matrix completion via convex optimization. Found Comput Math 9:717–772

    Article  MathSciNet  Google Scholar 

  32. Feng L, Sun H, Sun Q, Xia G (2016) Image compressive sensing via truncated schatten-p norm regularization. Signal Process Image Commun 47:28–41

    Article  Google Scholar 

  33. Gu S, Zhang L, Zuo W, Feng X (2014) Weighted nuclear norm minimization with application to image denoising. In Proceedings of the IEEE conference on computer vision and pattern recognition (CVPR), pp 2862–2869

  34. Zhang D, Hu Y, Ye J, Li X, He X (2012) Matrix completion by truncated nuclear norm regularization. In 2012 IEEE Conference on computer vision and pattern recognition, Providence, RI, Jun 16, pp 2192–2199

  35. Cao F, Chen J, Ye H, Zhao J, Zhou Z (2017) Recovering low-rank and sparse matrix based on the truncated nuclear norm. Neural Netw 85:10–20

    Article  PubMed  Google Scholar 

  36. Xue Z, Dong J, Zhao Y, Liu C, Chellali R (2019) Low-rank and sparse matrix decomposition via the truncated nuclear norm and a sparse regularizer. The Vis Comput 35(11):1549–1566

    Article  Google Scholar 

  37. Nie F, Wang H, Cai X, Huang H, Ding C (2012) Robust matrix completion via joint schatten p-norm and lp-norm minimization. In 2012 IEEE 12th International Conference on Data Mining, Brussels, Belgium, Dec 10, pp 566–574

  38. Xie Y, Gu S, Liu Y, Zuo W, Zhang W, Zhang L (2016) Weighted Schatten $ p $-norm minimization for image denoising and background subtraction. IEEE Trans Image Process 25(10):4842–4857

    Article  ADS  MathSciNet  Google Scholar 

  39. Dong W, Shi G, Li X, Ma Y, Huang F (2014) Compressive sensing via nonlocal low-rank regularization. IEEE Trans Image Process 23(8):3618–3632

    Article  ADS  MathSciNet  PubMed  Google Scholar 

  40. Kang Z, Peng C, Cheng Q (2015) Robust PCA via nonconvex rank approximation. In 2015 IEEE international conference on data mining, Atlantic City, NJ, Nov 14, pp 211–220

  41. Saeedi T, Rezghi M (2020) A novel enriched version of truncated nuclear norm regularization for matrix completion of inexact observed data. IEEE Trans Knowl Data Eng 34(2):519–530

    Article  Google Scholar 

  42. Hong B, Wei L, Hu Y, Cai D, He X (2016) Online robust principal component analysis via truncated nuclear norm regularization. Neurocomput 175:216–222

    Article  Google Scholar 

  43. Gu S, Xie Q, Meng D, Zuo W, Feng X, Zhang L (2017) Weighted nuclear norm minimization and its applications to low level vision. Int J Comput Vision 121:183–208

    Article  Google Scholar 

  44. Yang Z, Yang Z, Han D (2018) Alternating direction method of multipliers for sparse and low-rank decomposition based on nonconvex nonsmooth weighted nuclear norm. IEEE Access 6:56945–56953

    Article  Google Scholar 

  45. Jia X, Feng X, Wang W, Huang H, Xu C (2019) Online Schatten quasi-norm minimization for robust principal component analysis. Inf Sci 476:83–94

    Article  ADS  MathSciNet  Google Scholar 

  46. Shi X, Nie F, Lai Z, Guo Z (2018) Robust principal component analysis via optimal mean by joint ℓ2, 1 and Schatten p-norms minimization. Neurocomput 283:205–213

    Article  Google Scholar 

  47. Wen C, Qian W, Zhang Q, Cao F (2021) Algorithms of matrix recovery based on truncated Schatten p-norm. Int J Mach Learn Cybern 12:1557–1570

    Article  Google Scholar 

  48. Chen T, Zhao D, Sun L, Li S, Feng B (2023) Moving object detection via RPCA framework using non-convex low-rank approximation and total variational regularization. SIViP 17(1):109–117

    Article  Google Scholar 

  49. Yang Z, Yang Y, Fan L, Bao BK (2022) Truncated γ norm-based low-rank and sparse decomposition. Multimed Tools Appl 81(27):38279–38295

    Article  Google Scholar 

  50. Yang Y, Yang Z, Li J (2023) Novel RPCA with nonconvex logarithm and truncated fraction norms for moving object detection. Digit Signal Process 133:103892

    Article  Google Scholar 

  51. Wen F, Ying R, Liu P, Qiu RC (2019) Robust PCA using generalized nonconvex regularization. IEEE Trans Circuits Syst Video Technol 30(6):1497–1510

    Article  Google Scholar 

  52. Zheng QZ, Xu PF (2022) A unified framework for nonconvex nonsmooth sparse and low-rank decomposition by majorization-minimization algorithm. J Franklin Inst 359(16):9376–9400

    Article  MathSciNet  Google Scholar 

  53. Boyd S, Parikh N, Chu E, Peleato B, Eckstein J (2011) Distributed optimization and statistical learning via the alternating direction method of multipliers. Found Trends® Mach Learn 3(1):1–122

    Google Scholar 

  54. Hunter DR, Lange K (2004) A tutorial on MM algorithms. Am Stat 58(1):30–37

    Article  MathSciNet  Google Scholar 

  55. Cai J, Candes E, Shen Z (2008) A singular value thresholding algorithm for matrix completion. SIAM J Optim 20(4):1956–1982

    Article  MathSciNet  Google Scholar 

  56. Lin Z, Ganesh A, Wright J, Wu L, Chen M, Ma Y (2009) Fast convex optimization algorithms for exact recovery of a corrupted low-rank matrix. Coordinated Science Laboratory Report no. UILU-ENG-09–2214, DC-246

  57. Yuan X, Yang J (2009) Sparse and low-rank matrix decomposition via alternating direction methods. preprint, 12(2)

  58. Zhou Z, Li X, Wright J, Candes E, Ma Y (2010) Stable principal component pursuit. In 2010 IEEE international symposium on information theory, Austin, TX, Jun 13, pp 1518–1522

  59. Yang Z, Fan L, Yang Y, Yang Z, Gui G (2019) Generalized singular value thresholding operator based nonconvex low-rank and sparse decomposition for moving object detection. J Franklin Inst 356(16):10138–10154

    Article  MathSciNet  Google Scholar 

  60. Carrillo RE, Aysal TC, Barner KE (2010) A generalized cauchy distribution framework for problems requiring robust behavior. EURASIP J Adv Signal Process 1–19

  61. Rider PR (1957) Generalized cauchy distributions. Annals Inst Stat Math 9(1):215–223

    Article  MathSciNet  Google Scholar 

  62. Miller J, Thomas J (1972) Detectors for discrete- time signals in non- Gaussian noise. IEEE Trans on Inf Theory 18(2):241–250

    Article  Google Scholar 

  63. Carrillo RE, Barner KE, Aysal TC (2010) Robust sampling and reconstruction methods for sparse signals in the presence of impulsive noise. IEEE J Select Top Signal Process 4(2):392–408

    Article  ADS  Google Scholar 

  64. Carrillo RE, Barner KE (2013) Lorentzian iterative hard thresholding: robust compressed sensing with prior information. IEEE Trans Signal Process 61(19):4822–4833

    Article  ADS  MathSciNet  Google Scholar 

  65. Keshavarzian R, Aghagolzadeh A, Rezaii TY (2019) LLp norm regularization based group sparse representation for image compressed sensing recovery. Signal Process Image Commun 78:477–493

    Article  Google Scholar 

  66. Chen K, Dong H, Chan KS (2013) Reduced rank regression via adaptive nuclear norm penalization. Biometrika 100(4):901–920

    Article  MathSciNet  PubMed  Google Scholar 

  67. Lee KC, Ho J, Kriegman DJ (2005) Acquiring linear subspaces for face recognition under variable lighting. IEEE Trans Pattern Anal Mach Intell 27(5):684–698

    Article  PubMed  Google Scholar 

  68. Wong Z, Bovik AC, Sheikh HR, Simoncelli EP (2004) Image Quality Assessment: From Error Visibility to Structural Similarity. IEEE Trans Image Process 13(4):600–612

    Article  ADS  Google Scholar 

  69. Murali S, Govindan VK, Kalady S (2021) Quaternion-based image shadow removal. Vis Comput 38:1527–1538

    Article  Google Scholar 

  70. Wen F, Ying R, Liu P, Truong TK (2019) Nonconvex regularized robust PCA using the proximal block coordinate descent algorithm. IEEE Trans Signal Process 67(20):5402–5416

    Article  ADS  MathSciNet  Google Scholar 

Download references

Funding

The authors would like to acknowledge the funding support of Babol Noshirvani University of Technology through grant program No. BNUT/389059/1401.

Author information

Authors and Affiliations

  1. Department of Electrical Engineering, Heris Branch, Islamic Azad University, Heris, Iran

    Razieh Keshavarzian

  2. Faculty of Electrical and Computer Engineering, Babol Noshirvani University of Technology, Babol, Iran

    Ali Aghagolzadeh

Authors
  1. Razieh Keshavarzian
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Ali Aghagolzadeh
    View author publications

    You can also search for this author in PubMed Google Scholar

Contributions

All authors contributed to the study conception and design. Material preparation, data collection and analysis were performed by Razieh Keshavarzian and Ali Aghagolzadeh. The first draft of the manuscript was written by Razieh Keshavarzian and all authors commented on previous versions of the manuscript. All authors read and approved the final manuscript.

Corresponding author

Correspondence to Ali Aghagolzadeh.

Ethics declarations

Conflicts of Interests

The authors have no relevant financial or non-financial interests to disclose.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Keshavarzian, R., Aghagolzadeh, A. Low rank and sparse decomposition based on extended \({LL}_{p}\) norm. Multimed Tools Appl 83, 26107–26130 (2024). https://doi.org/10.1007/s11042-023-16584-3

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11042-023-16584-3

Keywords

Search

Navigation