Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Phương pháp phân chia cho các bài toán ràng buộc trực giao
Tóm tắt
Các bài toán ràng buộc trực giao được sử dụng rộng rãi trong khoa học và kỹ thuật. Tuy nhiên, việc giải quyết những bài toán này một cách hiệu quả gặp nhiều thách thức do các ràng buộc không lồi. Trong bài báo này, một phương pháp phân chia dựa trên vòng lặp Bregman được trình bày để giải quyết các bài toán tối ưu hóa với ràng buộc trực giao. Với phương pháp được đề xuất, các bài toán ràng buộc có thể được giải quyết theo kiểu lặp lại bằng cách tính toán các bài toán không ràng buộc tương ứng và các bài toán quadratique ràng buộc trực giao có giải pháp phân tích. Như là các ứng dụng, chúng tôi chứng minh tính mạnh mẽ của phương pháp của chúng tôi trong một số bài toán bao gồm việc điều chỉnh trường phương hướng, khôi phục hình ảnh màu có nhiễu và bản đồ biểu hình toàn cầu cho việc xây dựng các bề mặt loại genus-0. Cũng có các so sánh số liệu với các phương pháp hiện có để minh họa hiệu quả của các thuật toán của chúng tôi.
Từ khóa
#Phương pháp phân chia #bài toán tối ưu hóa #ràng buộc trực giao #vòng lặp Bregman #khôi phục hình ảnh màu.Tài liệu tham khảo
Gu, X., Yau, S.: Computing conformal structures of surfaces. Commun. Inf. Syst. 2(2), 121–146 (2002)
Gu, X., Yau, S.T.: Global conformal surface parameterization. In Symposium on Geometry Processing pp. 127–137 (2003)
Lai, R., Wen, Z., Yin, W., Gu, X., Lui, L.M.: Folding-free global conformal mapping for genus-0 surfaces by harmonic energy minimization. J. Sci. Comput. (2013, revision)
Perona, P.: Orientation diffusion. IEEE Trans. Image Process. 79, 12–49 (1998)
Lin, S.-Y., Luskin, M.: Relaxation methods for liquid crystal problems. SIAM J. Numer. Anal. 26, 1310–1324 (1989)
Cohen, R., Hardt, R., Kinderlehrer, D., Lin, S.Y., Luskin, M.: Minimum energy configurations for liquid crystals: computational results. In: Theory and Applications of Liquid Crystals (Minneapolis, MN, 1985). IMA vol. 5 in Mathematics and its Applications, pp. 99–121 (1987)
Cohen, R., Lin, S.Y., Luskin, M.: Relaxation and gradient methods for molecular orientation in liquid crystals. Comput. Phys. Commun. 53, 455–465 (1989)
Chan, T.F., Shen, J.: Variational restoration of nonflat image features: models and algorithms. SIAM J. Appl. Math. 61, 1338–1361 (2000)
Tang, B., Sapiro, G., Caselles, V.: Diffusion of general data on non-flat manifolds via harmonic maps theory: the direction diffusion case. Int. J. Comput. Vis. 36, 149–161 (2000)
Tang, B., Sapiro, G., Caselles, V.: Color image enhancement via chromaticity diffusion. IEEE Trans. Image Process. 10, 701–707 (2001)
Vese, L.A., Osher, S.J.: Numerical methods for \(p\)-harmonic flows and applications to image processing. SIAM J. Numer. Anal. 40(6), 2085–2104 (2002)
Kružík, M., Prohl, A.: Recent developments in the modeling, analysis, and numerics of ferromagnetism. SIAM Rev. 48(3), 439–483 (2006)
Goldfarb, D., Wen, Z., Yin, W.: A curvilinear search method for the p-harmonic flow on spheres. SIAM J. Imaging Sci. 2, 84–109 (2009)
Boufounos, P.T., Baraniuk, R.G.: 1-bit compressive sensing. In: Conference on Information Sciences and Systems (CISS), IEEE, pp. 16–21. (2008)
Laska, J.N., Wen, Z., Yin, W., Baraniuk, R.G.: Trust, but verify: fast and accurate signal recovery from 1-bit compressive measurements. IEEE Trans. Signal Process. 59(11), 5289 (2011)
Yan, M., Yang, Y., Osher, S.: Robust 1-bit compressive sensing using adaptive outlier pursuit. IEEE Trans. Signal Process. 60(7), 3868–3875 (2012)
Edelman, A., As, T., Arias, A., Smith, T., et al.: The geometry of algorithms with orthogonality constraints. SIAM J. Matrix Anal. Appl 20(2), 303–353 (1998)
Caboussat, A., Glowinski, R., Pons, V.: An augmented lagrangian approach to the numerical solution of a non-smooth eigenvalue problem. J. Numer. Math. 17(1), 3–26 (2009)
Burkard, R.E., Karisch, S.E., Rendl, F.: Qaplib-a quadratic assignment problem library. J. Glob. Optim. 10(4), 391–403 (1997)
Loiola, E.M., de Abreu, N.M.M., Boaventura-Netto, P.O., Hahn, P., Querido, T.: A survey for the quadratic assignment problem. Eur. J. Oper. Res. 176(2), 657–690 (2007)
Nocedal, J., Wright, S.J.: Numerical Optimization. Springer, New York (2006)
Bethuel, F., Brezis, H., Hélein, F.: Asymptotics for the minimization of a ginzburg-landau functional. Calc. Var. Partial. Differ. Equ. 1(2), 123–148 (1993)
Glowinski, R., Le Tallec, P.: Augmented Lagrangian and operator splitting methods in nonlinear mechanics, vol. 9. Society for Industrial and Applied Mathematics (1987)
Fortin, M., Glowinski, R.: Augmented Lagrangian methods: applications to the numerical solution of boundary-value problems, vol. 15. North Holland (2000)
Manton, J.H.: Optimization algorithms exploiting unitary constraints. IEEE Trans. Signal Process. 50(3), 635–650 (2002)
Yamada, I., Ezaki, T.: An orthogonal matrix optimization by dual cayley parametrization technique. In: 4th International Symposium on Independent Component Analysis and Blind, Signal Separation (ICA2003) (2003)
Absil, P.-A., Mahony, R., Sepulchre, R.: Optimization algorithms on matrix manifolds. Princeton University Press, Princeton (2008)
Wen, Z., Yin, W.: A feasible method for optimization with orthogonality constraints. Mathematical Programming, pp. 1–38 (2013)
Estellers, V., Zosso, D., Lai, R., Thiran, J.P., Osher, S., Bresson, X.: An efficient algorithm for level set method preserving distance function. IEEE Trans. Image Process. (2012, in press)
Glowinskiand, R., Holmstrom, M.: Constrained motion problems with applications by nonlinear programming methods. Surv. Math. Ind. 5, 75–108 (1995)
Osher, S., Burger, M., Goldfarb, D., Xu, J., Yin, W.: An iterative regularization method for total variation-based image restoration. Multiscale Model. Simul. 4(2), 460–489 (2005)
Yin, W., Osher, S., Goldfarb, D., Darbon, J.: Bregman iterative algorithms for \(\ell _1\)-minimization with applications to compressed sensing. SIAM J. Imaging Sci. 1(1), 143–168 (2008)
Yin, W., Osher, S.: Error forgetting of bregman iteration. UCLA CAM, Report (12–08) (2012)
Bregman, L.: The relaxation method of nding the common points of convex sets and its application to the solution of problems in convex optimization. USSR Comput. Math. Math. Phys. 7, 200–217 (1967)
Esser, E.: Applications of lagrangian-based alternating direction methods and connections to split bregman. UCLA CAM, Report (09–31) (2009)
Tai, X., Wu, C.: Augmented lagrangian method, dual methods and split bregman iteration for rof model. In: SSVM 09 Proceedings of the Second International Conference on Scale Space and Variational Methods in Computer Vision (2009)
Glowinski, R., Marrocco, A.: Sur lapproximation par elements finis dordre un, et la resolution par penalisation-dualite dune classe de problemes de dirichlet nonlineaires. Rev. Francaise dAut. Inf. Rech. Oper. R–2, 41–76 (1975)
Goldstein, T., Osher, S.: The split bregman method for l1 regularized problems. UCLA CAM Report 08-29 (2008)
Rosman, G., Wang, Y., Tai, X., Kimmel, R., Bruckstein, A.M.: Fast regularization of matrix-valued images. In: Computer Vision-ECCV 2012. pp. 173–186. Springer (2012)
Gibson, W.A.: On the least-squares orthogonalization of an oblique transformation. Psychometrika 27(2), 193–195 (1962)
Bethuel, F., Brezis, H., Helein, F.: Asymptotics for the minimization of a Ginzburg-Landau functional. Calc. Var. Partial. Differ. Equ. 1(2), 123–148 (1993)
Rudin, L., Osher, S., Fatemi, E.: Nonlinear total variation based noise removal algorithms. Physica. D. 60, 259–268 (1992)
Eck, M., DeRose, T., Duchamp, T., Hoppe, H., Lounsbery, M., Stuetzle, W.: Multiresolution analysis of arbitrary meshes. In: Proceeding of ACM SIGGRAPH (1995)
Kanai, T., Suzuki, H., Kimura, F.: Three-dimensional geometric metamorphosis based on harmonic maps. Vis. Comput. 14(4), 166–176 (1998)
Levy, B., Petitjean, S., Ray, N., Maillot, J.: Least squares conformal maps for automatic texture atlas generation. In: Proceeding of ACM SIGGRAPH (2002)
Alliez, P., Meyer, M., Desbrun, M.: Interactive geometry remeshing. In: Proceeding of ACM SIGGRAPH (2002)
Gu, X., Wang, Y., Chan, T.F., Thompson, P., Yau, S.T.: Genus zero surface conformal mapping and its application to brain surface mapping. IEEE Trans. Med. Imaging 23, 949–958 (2004)
Springborn, B., Schröder, P., Pinkall, U.: Conformal equivalence of triangle meshes. In: ACM Transactions on Graphics (TOG)—Proceedings of ACM SIGGRAPH 2008, vol. 27, no. 3. (2008)
Lui, L.M., Wang, Y., Thompson, P.M., Chan, T.F.: Landmark constrained genus zero surface conformal mapping and its application to brain mapping research. Appl. Numer. Math. 57, 847–858 (2007)
Lui, L.M., Gu, X., Chan, T.F., Yau, S.-T.: Variational method on riemann surfaces using conformal parameterization and its applications to image processing. Methods Appl. Anal. 15(4), 513–538 (2008)
Schoen, R., Yau, S.-T.: In: Lectures on Harmonic Maps. International Press, Cambridge (1994)
Jost, J.: Riemannian geometry and geometric analysis, 3rd edn. Springer, New York (2001)
Meyer, M., Desbrun, M., Schröder, P., Barr, A.H.: Discrete differential-geometry operators for triangulated 2-manifolds. In: Hege, H.C., Polthier, K. (eds.) Visualization and Mathematics III, pp. 35–57. Springer, New York (2003)
Desbrun, M., Meyer, M., Schröder, P., Barr, A.H.: Discrete differential geometry operators in nD. In: Proceedings of VisMath’02. Berlin, Germany (2002)
Xu, G: Convergent discrete laplace-beltrami operators over triangular surfaces. In: Proceedings of Geometric Modelling and Processing. pp. 195–204 (2004)