×

zbMATH — the first resource for mathematics

An efficient algorithm for batch images alignment with adaptive rank-correction term. (English) Zbl 1405.90053
Summary: With the appearance of approach named “robust alignment by sparse and low-rank decomposition” (RASL), a number of linearly correlated images can be accurately and robustly aligned despite significant corruptions and occlusions. It has been discovered that this aligning task can be characterized as a sequence of 3-block convex minimization problems which can be solved efficiently by the accelerated proximal gradient method (APG), or alternatively, by the directly extended alternating direction method of multipliers (ADMM). However, the directly extended ADMM may diverge although it often performs well in numerical computations. Ideally, one should find an algorithm which can have both theoretical guarantee and superior numerical efficiency over the directly extended ADMM. We achieve this goal by using the intelligent symmetric Gauss-Seidel iteration based ADMM (sGS-ADMM) which only needs to update one of the variables twice, but surprisingly, it leads to the desired convergence to be guaranteed. The convergence of sGS-ADMM can be followed directly by relating it to the classical 2-block ADMM and with a couple of specially designed semi-proximal terms. Beyond this, we also add a rank-correction term to the model with the purpose of deriving the alignment results with higher accuracy. The numerical experiments over a wide range of realistic misalignments demonstrate that sGS-ADMM is at least two times faster than RASL and APG for the vast majority of the tested problems.
MSC:
90B22 Queues and service in operations research
90C25 Convex programming
Software:
QSDPNAL; LFW
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Learned-Miller, E., Data driven image models through continuous joint alignment, IEEE Trans. Pattern Anal. Mach. Intell., 28, 2, 236-250, (2006)
[2] M. Cox, S. Lucey, S. Sridharan, J. Cohn, Least squares congealing for unsupervised alignment of images, in: Proc. IEEE Intl Conf. Computer Vision and Pattern Recognition, 2008.
[3] A. Vedaldi, G. Guidi, S. Soatto, Joint alignment up to (lossy) transformations, in: Proc. IEEE Intl Conf. Computer Vision and Pattern Recognition, 2008.
[4] Frey, B. J.; Jojic, N., Transformation-invariant clustering using the EM algorithm, IEEE Trans. Pattern Anal. Mach. Intell., 25, 1, 1-17, (2003)
[5] Peng, Y.; Ganesh, A.; Wright, J.; Xu, W.; Ma, Y., RASL: robust alignment by sparse and low-rank decomposition for linearly correlated images, IEEE Trans. Pattern Anal. Mach. Intell., 34, 2233-2246, (2012)
[6] Candès, E. J.; Li, X.; Ma, Y.; Wright, J., Robust principal component analysis?, J. ACM, 58, 1-37, (2011) · Zbl 1327.62369
[7] Zhang, Z.; Ganesh, A.; Liang, X.; Ma, Y., TILT: transform invariant low-rank textures, Int. J. Comput. Vis., 99, 1, 1-24, (2012) · Zbl 1254.68290
[8] Y. Peng, A. Ganesh, J. Wright, W. Xu, Y. Ma, RASL: Robust alignment by sparse and low-rank decomposition for linearly correlated images, in: Proc. IEEE Intl Conf. Computer Vision and Pattern Recognition, 2010.
[9] Chen, C. H.; He, B.; Ye, Y.; Yuan, X., The direct extension of ADMM for multi-block convex minimization problems is not necessarily convergent, Math. Program., 155, 57-79, (2016) · Zbl 1332.90193
[10] Liu, G.; Lin, Z.; Yan, S.; Sun, J.; Yu, Y.; Ma, Y., Robust recovery of subspace structures by low-rank representation, IEEE Trans. Pattern Anal. Mach. Intell., 35, 1, 171-184, (2013)
[11] Shi, C., Low-rank and sparse decomposition based shape model and probabilistic atlas for automatic pathological organ segmentation, Med. Image Anal., 38, 30-49, (2017)
[12] Xiao, Y.; Wu, S.-Y.; Li, D.-H., Splitting and linearizing augmented Lagrangian algorithm for subspace recovery from corrupted observations, Adv. Comput. Math., 38, 837-858, (2013) · Zbl 1269.65057
[13] Li, X. D.; Sun, D. F.; Toh, K.-C., A Schur complement based semi-proximal ADMM for convex quadratic conic programming and extensions, Math. Program., 155, 333-373, (2016) · Zbl 1342.90134
[14] Sun, D. F.; Toh, K.-C.; Yang, L., A convergent 3-block semi-proximal alternating direction method of multipliers for conic programming with 4-type constraints, SIAM J. Optim., 25, 882-915, (2015) · Zbl 1328.90083
[15] Chen, L.; Sun, D. F.; Toh, K.-C., An efficient inexact symmetric Gauss-Seidel based majorized ADMM for high-dimensional convex composite conic programming, Math. Program., 161, 1, 237-270, (2017) · Zbl 1356.90105
[16] X.D. Li, D.F. Sun, K.-C. Toh, QSDPNAL: A two-phase proximal augmented Lagrangian method for convex quadratic semidefinite programming, Math. Program. Comput. (2018) http://dx.doi.org/10.1007/s12532-018-0137-6.
[17] Y. Ding, Y. Xiao, Symmetric Gauss-Seidel technique based alternating direction methods of multipliers for transform invariant low-rank textures problem, J. Math. Imaging Vis. (2018) http://dx.doi.org/10.1007/s10851-018-0808-y. · Zbl 1433.68512
[18] Miao, W.; Pan, S.; Sun, D. F., A rank-corrected procedure for matrix completion with fixed basis coefficients, Math. Program., 159, 289-338, (2016) · Zbl 1356.90178
[19] X.D. Li, D.F. Sun, K.-C. Toh, A block symmtric Gauss-Seidel decomposition theorem for convex composite quadratic programming and its applications, Math. Program. (2018) http://dx.doi.org/10.1007/s10107-018-1247-7.
[20] Fazel, M.; Pong, T. K.; Sun, D. F.; Tseng, P., Hankel matrix rank minimization with applications in system identification and realization, SIAM J. Matrix Anal. Appl., 34, 946-977, (2013) · Zbl 1302.90127
[21] Rockafellar, R. T., Convex analysis, (1970), Princeton University Press · Zbl 0229.90020
[22] Ding, C., An introduction to a class of matrix optimization problems, (2012), National University of Singapore, (Ph.D. thesis)
[23] Cai, J. F.; Candès, E. J.; Shen, Z., A singular value thresholding algorithm for matrix completion, SIAM J. Optim., 20, 1956-1982, (2010) · Zbl 1201.90155
[24] Glowinski, R.; Marrocco, A., Sur l’approximation, par éléments finis d’ordre un, et la résolution, par pénalisation-dualité d’une classe de problèmes de Dirichlet non linéaires, Rev. Fr. Autom. Inform. Rech. Opér. Anal. Numér., 9, 2, 41-76, (1975) · Zbl 0368.65053
[25] Gabay, D.; Mercier, B., A dual algorithm for the solution of nonlinear variational problems via finite element approximation, Comput. Math. Appl., 2, 17-40, (1976) · Zbl 0352.65034
[26] Eckstein, J., Some saddle-function splitting methods for convex programming, Optim. Methods Softw., 4, 75-83, (1994)
[27] Nesterov, Y. E., A method for solving the convex programming problem with convergence rate \(O(1 / k^2)\), Dokl. Akad. Nauk SSSR, 269, 543-547, (1983), (in Russian)
[28] Gary B. Huang, Manu Ramesh, Tamara Berg, Erik Learned-Miller, Labeled Faces in the Wild: A Database for Studying Face Recognition in Unconstrained Environments, University of Massachusetts, Amherst, Technical Report 07-49, 2007.
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.