Fast Randomized Singular Value Thresholding for Low-Rank Optimization

Cited 21 time in webofscience Cited 0 time in scopus
  • Hit : 350
  • Download : 0
DC FieldValueLanguage
dc.contributor.authorOh, Tae-Hyunko
dc.contributor.authorMatsushita, Yasuyukiko
dc.contributor.authorTai, Yu-Wingko
dc.contributor.authorKweon, In-Soko
dc.date.accessioned2018-02-21T05:34:04Z-
dc.date.available2018-02-21T05:34:04Z-
dc.date.created2016-12-29-
dc.date.created2016-12-29-
dc.date.issued2018-02-
dc.identifier.citationIEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, v.40, no.2, pp.376 - 391-
dc.identifier.issn0162-8828-
dc.identifier.urihttp://hdl.handle.net/10203/240091-
dc.description.abstractRank minimization can be converted into tractable surrogate problems, such as Nuclear Norm Minimization (NNM) and Weighted NNM (WNNM). The problems related to NNM, or WNNM, can be solved iteratively by applying a closed-form proximal operator, called Singular Value Thresholding (SVT), or Weighted SVT, but they suffer from high computational cost of Singular Value Decomposition (SVD) at each iteration. We propose a fast and accurate approximation method for SVT, that we call fast randomized SVT (FRSVT), with which we avoid direct computation of SVD. The key idea is to extract an approximate basis for the range of the matrix from its compressed matrix. Given the basis, we compute partial singular values of the original matrix from the small factored matrix. In addition, by developping a range propagation method, our method further speeds up the extraction of approximate basis at each iteration. Our theoretical analysis shows the relationship between the approximation bound of SVD and its effect to NNM via SVT. Along with the analysis, our empirical results quantitatively and qualitatively show that our approximation rarely harms the convergence of the host algorithms. We assess the efficiency and accuracy of the proposed method on various computer vision problems, e.g., subspace clustering, weather artifact removal, and simultaneous multi-image alignment and rectification.-
dc.languageEnglish-
dc.publisherIEEE COMPUTER SOC-
dc.subjectMATRIX COMPLETION-
dc.subjectMINIMIZATION-
dc.subjectAPPROXIMATION-
dc.subjectDECOMPOSITION-
dc.subjectALGORITHMS-
dc.subjectNORM-
dc.titleFast Randomized Singular Value Thresholding for Low-Rank Optimization-
dc.typeArticle-
dc.identifier.wosid000422706000009-
dc.identifier.scopusid2-s2.0-85040654085-
dc.type.rimsART-
dc.citation.volume40-
dc.citation.issue2-
dc.citation.beginningpage376-
dc.citation.endingpage391-
dc.citation.publicationnameIEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE-
dc.identifier.doi10.1109/TPAMI.2017.2677440-
dc.contributor.localauthorTai, Yu-Wing-
dc.contributor.localauthorKweon, In-So-
dc.contributor.nonIdAuthorMatsushita, Yasuyuki-
dc.description.isOpenAccessN-
dc.type.journalArticleArticle-
dc.subject.keywordAuthorSingular value thresholding-
dc.subject.keywordAuthorrank minimization-
dc.subject.keywordAuthornuclear norm minimization-
dc.subject.keywordAuthorrobust principal component analysis-
dc.subject.keywordAuthorlow-rank approximation-
dc.subject.keywordPlusMATRIX COMPLETION-
dc.subject.keywordPlusMINIMIZATION-
dc.subject.keywordPlusAPPROXIMATION-
dc.subject.keywordPlusDECOMPOSITION-
dc.subject.keywordPlusALGORITHMS-
dc.subject.keywordPlusNORM-
Appears in Collection
EE-Journal Papers(저널논문)
Files in This Item
There are no files associated with this item.
This item is cited by other documents in WoS
⊙ Detail Information in WoSⓡ Click to see webofscience_button
⊙ Cited 21 items in WoS Click to see citing articles in records_button

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0