Top

International Journal of Computer Vision

Published in:

01-08-2013

Linearized Alternating Direction Method with Adaptive Penalty and Warm Starts for Fast Solving Transform Invariant Low-Rank Textures

Authors: Xiang Ren, Zhouchen Lin

Published in: International Journal of Computer Vision | Issue 1/2013

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Transform invariant low-rank textures (TILT) is a novel and powerful tool that can effectively rectify a rich class of low-rank textures in 3D scenes from 2D images despite significant deformation and corruption. The existing algorithm for solving TILT is based on the alternating direction method. It suffers from high computational cost and is not theoretically guaranteed to converge to a correct solution to the inner loop. In this paper, we propose a novel algorithm to speed up solving TILT, with guaranteed convergence for the inner loop. Our method is based on the recently proposed linearized alternating direction method with adaptive penalty. To further reduce computation, warm starts are also introduced to initialize the variables better and cut the cost on singular value decomposition. Extensive experimental results on both synthetic and real data demonstrate that this new algorithm works much more efficiently and robustly than the existing algorithm. It could be at least five times faster than the previous method.

next article SLEDGE: Sequential Labeling of Image Edges for Boundary Detection

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Available only for authorised users

For the case of more than two variables, ADM with some appropriate modifications, such as introducing a dummy variable and treating all the original variables as a super block (Bertsekas and Tsitsiklis 1997) or introducing a Gaussian back substitution (He et al. 2012), can be proven to converge.

Please refer to (20) and (23). For succinctness, we do not repeat it here. Disregarding the adaptive penalty, LADMAP is a special case of the generalized ADM (Deng and Yin 2012) and is closely related to the predictor corrector proximal multiplier method (Chen and Teboulle 1994) which updates variables parallelly rather than alternately.

A Stiefel manifold is a set of columnly orthonormal matrices whose geodesic distance is induced from the Euclidian distance of its ambient space.

We will see much higher acceleration rates when using SVDWS on real data (see Sect. 6.2.3).

Note that as the whole TILT problem (2) is not a convex program, LADMAP cannot achieve the global optimum either. So LADMAP can also fail to recover the correct deformation.

Bertsekas, D., & Tsitsiklis, J. (1997). Parallel and distributed computation: Numerical methods. Cambridge: Athena Scientific.

Cai, J., Candés, E., & Shen, Z. (2010). A singular value thresholding algorithm for matrix completion. SIAM Journal on Optimization, 20(4), 1956–1982.MathSciNetMATHCrossRef

Candés, E., Li, X., Ma, Y., & Wright, J. (2011). Robust principal component analysis? Journal of the ACM, 58(3), 1–37.CrossRef

Chen, G., & Teboulle, M. (1994). A proximal-based decomposition method for convex minimization problems. Mathematical Programming, 64(1), 81–101.MathSciNetMATHCrossRef

Deng, W., & Yin, W. (2012). On the global and linear convergence of the generalized alternating direction method of multipliers. Rice University Technical Report. Houston: Rice University.

Donoho, D. (1995). De-noising by soft-thresholding. IEEE Transaction on Information Theory, 41(3), 613–627.MathSciNetMATHCrossRef

Donoho, D. (2004). For most large underdetermined systems of linear equations the minimal \(\ell _1\)-norm solution is also the sparsest solution. Communications on Pure and Applied Mathematics, 59(6), 797–829.MathSciNetCrossRef

Edelman, A., Arias, T., & Smith, S. (1999). The geometry of algorithms with orthogonality constraints. SIAM Journal on Matrix Analysis and Applications, 20(2), 303–353.MathSciNetCrossRef

He, B., Tao, M., & Yuan, X. (2012). Alternating direction method with Gaussian back substitution for separable convex programming. SIAM Journal on Optimization, 22(2), 313–340.MathSciNetMATHCrossRef

Lin, Z., Chen, M., & Ma, Y. (2009). The augmented Lagrange multiplier method for exact recovery of corrupted low-rank matrices. UIUC Technical, Report UILU-ENG-09-2215. Urbana: UIUC.

Lin, Z., Liu, R., & Su, Z. (2011). Linearized alternating direction method with adaptive penalty for low-rank representation. In Advances in Neural Information Processing System. Granada: NIPS.

Liu, G., Lin, Z., & Yu, Y. (2010). Robust subspace segmentation by low-rank representation. In International Conference on Machine Learning. Haifa: ICML.

Mobahi, H., Zhou, Z., Yang, A., & Ma, Y. (2011). Holistic 3D reconstruction of urban structures from low-rank textures. In IEEE Workshop on 3D Representation and Recognition (3dRR-11). Barcellona: IEEE.

Peng, Y., Ganesh, A., Wright, J., Xu, W., & Ma, Y. (2010). RASL: Robust alignment by sparse and low-rank decomposition for linearly correlated images. In IEEE Conference on Computer Vision and Pattern Recognition. San Francisco: IEEE.

Pierra, G. (1984). Decomposition through formalization in a product space. Mathematical Programming, 28, 96–115.

Schindler, G., Krishnamurthy, P., Lublinerman, R., Liu, Y., & Dellaert, F. (2008). Detecting and matching repeated patterns for automatic geo-tagging in urban environments. In IEEE Conference on Computer Vision and Pattern Recognition. Anchorage: IEEE.

Toh, K., & Yun, S. (2009). An accelerated proximal gradient algorithm for nuclear norm regularized least squares problems. Pacific Journal of Optimization, 6, 615–640.

Wen, Z., & Yin, W. (2013). A feasible method for optimization with orthogonality constraints. Mathematical Programming, accepted.

Yang, J., & Zhang, Y. (2011). Alternating direction algorithms for \(l_1\) problems in compressive sensing. SIAM Journal on Scientific Computing, 33(1), 250–278.MathSciNetMATHCrossRef

Zhang, Z., Liang, X., & Ma, Y. (2011a). Unwrapping low-rank textures on generalized cylindrical surfaces. In IEEE Conference on Computer Vision and Pattern Recognition. Colorado Springs: IEEE.

Zhang, Z., Matsushita, Y., & Ma, Y. (2011b). Camera calibration with lens distortion from low-rank textures. In IEEE Conference on Computer Vision and Pattern Recognition. Colorado Springs: IEEE.

Zhang, X., Lin, Z., Sun, F., & Ma, Y. (2012a). Rectification of Chinese characters as transform invariant low-rank textures. Pattern Recognition (submitted to).

Zhang, Z., Ganesh, A., Liang, X., & Ma, Y. (2012b). TILT: Transform-invariant low-rank textures. International Journal of Computer Vision (IJCV), 99(1), 1–24.MathSciNetMATHCrossRef

Zhao, P., & Quan, L. (2011). Translation symmetry detection in a fronto-parallel view. In IEEE Conference on Computer Vision and Pattern Recognition. Colorado Springs: IEEE.

Title: Linearized Alternating Direction Method with Adaptive Penalty and Warm Starts for Fast Solving Transform Invariant Low-Rank Textures
Authors: Xiang Ren
Zhouchen Lin
Publication date: 01-08-2013
Publisher: Springer US
Published in: International Journal of Computer Vision / Issue 1/2013
Print ISSN: 0920-5691
Electronic ISSN: 1573-1405
DOI: https://doi.org/10.1007/s11263-013-0611-6

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Other articles of this Issue 1/2013

Recovering Relative Depth from Low-Level Features Without Explicit T-junction Detection and Interpretation

3D Scene Reconstruction from Multiple Spherical Stereo Pairs

SLEDGE: Sequential Labeling of Image Edges for Boundary Detection

Coupling Image Restoration and Segmentation: A Generalized Linear Model/Bregman Perspective

Premium Partner