Linearized alternating direction method with adaptive penalty and warm starts for fast solving transform invariant low-rank textures. (English) Zbl 1270.68354
Summary: 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.
Keywords:
transform invariant low-rank textures; linearized alternating direction method with adaptive penalty; warm start; singular value decompositionSoftware:
RASLReferences:
| [1] | Bertsekas, D., & Tsitsiklis, J. (1997). Parallel and distributed computation: Numerical methods. Cambridge: Athena Scientific. · Zbl 0743.65107 |
| [2] | Cai, J., Candés, E., & Shen, Z. (2010). A singular value thresholding algorithm for matrix completion. SIAM Journal on Optimization, 20(4), 1956–1982. · Zbl 1201.90155 · doi:10.1137/080738970 |
| [3] | Candés, E., Li, X., Ma, Y., & Wright, J. (2011). Robust principal component analysis? Journal of the ACM, 58(3), 1–37. · Zbl 1327.62369 · doi:10.1145/1970392.1970395 |
| [4] | Chen, G., & Teboulle, M. (1994). A proximal-based decomposition method for convex minimization problems. Mathematical Programming, 64(1), 81–101. · Zbl 0823.90097 · doi:10.1007/BF01582566 |
| [5] | 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. · Zbl 1379.65036 |
| [6] | Donoho, D. (1995). De-noising by soft-thresholding. IEEE Transaction on Information Theory, 41(3), 613–627. · Zbl 0820.62002 · doi:10.1109/18.382009 |
| [7] | Donoho, D. (2004). For most large underdetermined systems of linear equations the minimal $$\(\backslash\)ell _1$$ -norm solution is also the sparsest solution. Communications on Pure and Applied Mathematics, 59(6), 797–829. · Zbl 1113.15004 · doi:10.1002/cpa.20132 |
| [8] | 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. · Zbl 0928.65050 · doi:10.1137/S0895479895290954 |
| [9] | 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. · Zbl 1273.90152 · doi:10.1137/110822347 |
| [10] | 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. |
| [11] | 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. |
| [12] | Liu, G., Lin, Z., & Yu, Y. (2010). Robust subspace segmentation by low-rank representation. In International Conference on Machine Learning. Haifa: ICML. |
| [13] | 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. |
| [14] | 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. |
| [15] | Pierra, G. (1984). Decomposition through formalization in a product space. Mathematical Programming, 28, 96–115. · Zbl 0523.49022 |
| [16] | 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. |
| [17] | Toh, K., & Yun, S. (2009). An accelerated proximal gradient algorithm for nuclear norm regularized least squares problems. Pacific Journal of Optimization, 6, 615–640. · Zbl 1205.90218 |
| [18] | Wen, Z., & Yin, W. (2013). A feasible method for optimization with orthogonality constraints. Mathematical Programming, accepted. · Zbl 1281.49030 |
| [19] | Yang, J., & Zhang, Y. (2011). Alternating direction algorithms for $$l_1$$ problems in compressive sensing. SIAM Journal on Scientific Computing, 33(1), 250–278. · Zbl 1256.65060 · doi:10.1137/090777761 |
| [20] | 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. |
| [21] | 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. |
| [22] | Zhang, X., Lin, Z., Sun, F., & Ma, Y. (2012a). Rectification of Chinese characters as transform invariant low-rank textures. Pattern Recognition (submitted to). |
| [23] | 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. · Zbl 1254.68290 · doi:10.1007/s11263-012-0515-x |
| [24] | 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. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
