×

Symmetric Gauss-Seidel technique-based alternating direction methods of multipliers for transform invariant low-rank textures problem. (English) Zbl 1433.68512

Summary: Transform invariant low-rank textures, referred to as TILT, can accurately and robustly extract textural or geometric information in a 3D from user-specified windows in 2D in spite of significant corruptions and warping. It was discovered that the task can be characterized, both theoretically and numerically, by solving a sequence of matrix nuclear-norm and \(\ell _1\)-norm involved convex minimization problems. For solving this problem, the direct extension of alternating direction method of multipliers (ADMM) in an usual Gauss-Seidel manner often performs numerically well in practice but there is no theoretical guarantee on its convergence. In this paper, we resolve this dilemma by using the novel symmetric Gauss-Seidel (sGS)-based ADMM developed by X. Li et al. [Math. Program. 155, No. 1–2 (A), 333–373 (2016; Zbl 1342.90134)]. The sGS-ADMM is guaranteed to converge, and we shall demonstrate in this paper that it is also practically efficient than the directly extended ADMM. When the sGS technique is applied to this particular problem, we show that only one variable needs to be re-updated, and this updating hardly imposes any excessive computational cost. The sGS decomposition theorem of X. Li et al. [Math. Program. 175, No. 1–2 (A), 395–418 (2019; Zbl 1412.90086)] establishes the equivalent between sGS-ADMM and the classical ADMM with an additional semi-proximal term, so the convergence result is followed directly. Extensive experiments illustrate that the sGS-ADMM and its generalized variant have superior numerical efficiency over the directly extended ADMM.

MSC:

68U10 Computing methodologies for image processing
65F10 Iterative numerical methods for linear systems
90C25 Convex programming

Software:

ASIFT; RASL; SIFT; QSDPNAL
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Cai, JF; Candès, EJ; Shen, Z, A singular value thresholding algorithm for matrix completion, SIAM J. Optim., 20, 1956-1982, (2010) · Zbl 1201.90155 · doi:10.1137/080738970
[2] Candès, EJ; Li, X; Ma, Y; Wright, J, Robust principal component analysis?, J. ACM, 58, 1-37, (2011) · Zbl 1327.62369 · doi:10.1145/1970392.1970395
[3] Chen, C.H.: Numerical algorithms for a class of matrix norm approximation problems, Ph.D. thesis, Department of Mathematics, Nanjing University, Nanjing, China. http://www.math.nus.edu.sg/ matsundf/Thesis_Caihua.pdf (2012)
[4] Chen, CH; He, B; Ye, Y; Yuan, X, The direct extension of ADMM for multi-block convex minimization problems is not necessarily convergent, Math. Progrm., 155, 57-79, (2016) · Zbl 1332.90193 · doi:10.1007/s10107-014-0826-5
[5] Chen, L; Sun, DF; Toh, K-C, An efficient inexact symmetric Gauss-Seidel based majorized ADMM for high-dimensional convex composite conic programming, Math. Program., 161, 237-270, (2017) · Zbl 1356.90105 · doi:10.1007/s10107-016-1007-5
[6] Eckstein, J, Some saddle-function splitting methods for convex programming, Optim. Methods Softw., 4, 75-83, (1994) · doi:10.1080/10556789408805578
[7] Eckstein, J; Bertsekas, DP, On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators, Math. Program., 55, 293-318, (1992) · Zbl 0765.90073 · doi:10.1007/BF01581204
[8] Fazel, M.: Matrix rank minimization with applications, Ph.D. thesis, Stanford University (2002)
[9] Fazel, M; Pong, TK; Sun, DF; 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 · doi:10.1137/110853996
[10] 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 · doi:10.1016/0898-1221(76)90003-1
[11] 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, revue française d’atomatique, informatique recherche opérationelle, Analyse Numérique, 9, 41-76, (1975) · Zbl 0368.65053 · doi:10.1051/m2an/197509R200411
[12] Lam, X.Y., Marron, J.S., Sun, D.F., Toh, K.-C.: Fast algorithms for large scale generalized distance weighted discrimination (2017). arXiv:1604.05473v4
[13] Li, XD; Sun, DF; 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 · doi:10.1007/s10107-014-0850-5
[14] Li, X.D., Sun, D.F., Toh, K.-C.: QSDPNAL: A two-phase proximal augmented Lagrangian method for convex quadratic semidefinite programming (2016). arXiv:1512.08872v1
[15] Li, X.D., Sun, D.F., Toh, K.-C.: A block symmetric Gauss-Seidel decomposition theorem for convex composite quadratic programming and its applications. Math. Program. (2018). https://doi.org/10.1007/s10107-018-1247-7
[16] Lowe, DG, Distinctive image features from scale-invariant keypoints, Int. J. Comput. Vis., 60, 91-110, (2004) · doi:10.1023/B:VISI.0000029664.99615.94
[17] Miao, W; Pan, S; Sun, DF, A rank-corrected procedure for matrix completion with fixed basis coefficients, Math. Program., 159, 289-338, (2016) · Zbl 1356.90178 · doi:10.1007/s10107-015-0961-7
[18] Morel, JM; Yu, G, ASIFT: a new framework for fully affine invariant image comparison, SIAM J. Imaging Sci., 2, 438-469, (2009) · Zbl 1181.68252 · doi:10.1137/080732730
[19] 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., 34, 2233-2246, (2012) · doi:10.1109/TPAMI.2011.282
[20] Ren, X; Lin, Z, Linearized alternating direction method with adaptive penalty and warm starts for fast solving transform invariant low-rank textures, Int. J. Comput. Vis., 104, 1-14, (2013) · Zbl 1270.68354 · doi:10.1007/s11263-013-0611-6
[21] Rockafellar, R.T.: Convex analysis. Princeton University Press, New York (1970) · Zbl 0193.18401 · doi:10.1515/9781400873173
[22] Sun, DF; 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 · doi:10.1137/140964357
[23] Xiao, Y., Chen, L., Li, D.H.: A generalized alternating direction method of multipliers with semi-proximal terms for convex composite conic programming (2017). arXiv:1507.05691v3
[24] Xiao, Y; Song, H, An inexact alternating directions algorithm for constrained total variation regularized compressive sensing problems, J. Math. Imaging Vis., 44, 114-127, (2012) · Zbl 1255.94030 · doi:10.1007/s10851-011-0314-y
[25] Xiao, Y; Yang, J; Yuan, X, Alternating algorithms for toal variation image reconstuction from random projections, Inverse Probl. Imag., 6, 547-563, (2012) · Zbl 1260.94023 · doi:10.3934/ipi.2012.6.547
[26] Yang, J; Zhang, Y, Alternating direction algorithm for \(ℓ _1\)-problems for compressive sensing, SIAM J. Sci. Comput., 33, 250-273, (2011) · Zbl 1256.65060 · doi:10.1137/090777761
[27] Zhang, Z; Ganesh, A; Liang, X; Ma, Y, TILT: transform invariant low-rank textures, Int. J. Comput. Vis., 99, 1-24, (2012) · Zbl 1254.68290 · doi:10.1007/s11263-012-0515-x
[28] Zhang, Z., Liang, X., Ma, Y.: Unwrapping low-rank textures on generalized cylindrical surfaces. In: Proceedings of International Conference on Computer Vision (ICCV), pp. 1347-1354.
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.