Hostname: page-component-586b7cd67f-r5fsc Total loading time: 0 Render date: 2024-11-22T08:14:55.012Z Has data issue: false hasContentIssue false
  • English
  • Français

DOUGLAS–RACHFORD FEASIBILITY METHODS FOR MATRIX COMPLETION PROBLEMS

Part of: Miscellaneous applications of operator theory

Published online by Cambridge University Press:  25 July 2014

FRANCISCO J. ARAGÓN ARTACHO ,
JONATHAN M. BORWEIN  and
MATTHEW K. TAM
FRANCISCO J. ARAGÓN ARTACHO
Affiliation:
Systems Biochemistry Group, Luxembourg Centre for Systems Biomedicine, University of Luxembourg, Campus Belval, L-4362 Esch-sur-Alzette, Luxembourg email [email protected] Address when work was performed: CARMA Centre, University of Newcastle, Callaghan, NSW 2308, Australia email [email protected]
JONATHAN M. BORWEIN
Affiliation:
CARMA Centre, University of Newcastle, Callaghan, NSW 2308, Australia email [email protected]
MATTHEW K. TAM*
Affiliation:
CARMA Centre, University of Newcastle, Callaghan, NSW 2308, Australia email [email protected]
*
✉[email protected]
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

In this paper, we give general recommendations for successful application of the Douglas–Rachford reflection method to convex and nonconvex real matrix completion problems. These guidelines are demonstrated by various illustrative examples.

Keywords

Douglas–Rachford projectionsreflectionsmatrix completionfeasibility problemsprotein reconstructionHadamard matrices

MSC classification

Secondary: 90C59: Approximation methods and heuristics 47N10: Applications in optimization, convex analysis, mathematical programming, economics
Type
Research Article
Information
The ANZIAM Journal , Volume 55 , Issue 4 , April 2014 , pp. 299 - 326
Copyright
Copyright © 2014 Australian Mathematical Society 

References

Ammar, G., Benner, P. and Mehrmann, V., “A multishift algorithm for the numerical solution of algebraic Riccati equations”, Electron. Trans. Numer. Anal. 1 (1993) 33–48.Google Scholar
Aragón Artacho, F. J. and Borwein, J. M., “Global convergence of a non-convex Douglas–Rachford iteration”, J. Global Optim. 57 (2013) 753–769; doi:10.1007/s10898-012-9958-4.CrossRefGoogle Scholar
Aragón Artacho, F. J., Borwein, J. M. and Tam, M. K., “Recent results on Douglas–Rachford method for combinatorial optimization problems”, J. Optim. Theory Appl. (2013) ;doi:10.1007/s10957-013-0488-0.Google Scholar
Bačák, M., Searston, M. I. and Sims, I. B., “Alternating projections in CAT(0) spaces”, J. Math. Anal. Appl. 385 (2012) 599–607.CrossRefGoogle Scholar
Bauschke, H. H. and Borwein, J. M., “On the convergence of von Neumann’s alternating projection algorithm for two sets”, Set-Valued Anal. 1 (1993) 185–212; doi:10.1007/BF01027691.CrossRefGoogle Scholar
Bauschke, H. H. and Borwein, J. M., “Dykstra’s alternating projection algorithm for two sets”, J. Approx. Theory 79 (1994) 418–443; doi:10.1006/jath.1994.1136.CrossRefGoogle Scholar
Bauschke, H. H. and Borwein, J. M., “On projection algorithms for solving convex feasibility problems”, SIAM Rev. 38 (1996) 367–426; doi:10.1137/S0036144593251710.CrossRefGoogle Scholar
Bauschke, H. H., Borwein, J. M. and Lewis, A., “The method of cyclic projections for closed convex sets in Hilbert space”, Contemp. Math. 204 (1997) 1–38; doi:10.1090/conm/204/02620.CrossRefGoogle Scholar
Bauschke, H. H., Combettes, P. L. and Luke, D. R., “Phase retrieval, error reduction algorithm, and Fienup variants: a view from convex optimization”, J. Opt. Soc. Amer. A 19 (2002) 1334–1345 ;doi:10.1364/JOSAA.19.001334.CrossRefGoogle ScholarPubMed
Bauschke, H. H., Combettes, P. L. and Luke, D. R., “Hybrid projection–reflection method for phased retrieval”, J. Opt. Soc. Amer. A 20 (2003) 1025–1034; doi:10.1364/JOSAA.20.001025.CrossRefGoogle Scholar
Bauschke, H. H., Combettes, P. L. and Luke, D. R., “Finding best approximation pairs relative to two closed convex sets in Hilbert space”, J. Approx. Theory 127 (2004) 178–192 ;doi:10.1016/j.jat.2004.02.006.CrossRefGoogle Scholar
Birgin, E. G. and Raydan, M., “Robust stopping criteria for Dykstra’s algorithm”, SIAM J. Sci. Comput. 26 (2005) 1405–1414; doi:10.1137/03060062X.CrossRefGoogle Scholar
Borwein, J. M. and Lewis, A. S., Convex analysis and nonlinear optimization (Springer, New York, 2006).CrossRefGoogle Scholar
Borwein, J. M. and Luke, D. R., “Entropic regularization of the $\def \xmlpi #1{}\def \mathsfbi #1{\boldsymbol {\mathsf {#1}}}\let \le =\leqslant \let \leq =\leqslant \let \ge =\geqslant \let \geq =\geqslant \def \Pr {\mathit {Pr}}\def \Fr {\mathit {Fr}}\def \Rey {\mathit {Re}}\ell _0$ function”, in: Fixed-point algorithms for inverse problems in science and engineering (Springer, New York, 2011), 65–92.CrossRefGoogle Scholar
Borwein, J. M. and Sims, B., “The Douglas–Rachford algorithm in the absence of convexity”, in: Fixed-point algorithms for inverse problems in science and engineering (Springer, New York, 2011), 93–109.CrossRefGoogle Scholar
Borwein, J. M. and Tam, M. K., “A cyclic Douglas–Rachford iteration scheme”, J. Optim. Theory Appl. 160 (2014) 1–29; doi:10.1007/s10957-013-0381-x.CrossRefGoogle Scholar
Boyle, J. and Dykstra, R., “A method for finding projections onto the intersection of convex sets in Hilbert spaces”, Lecture Notes in Statist. 37 (1986) 28–47; doi:10.1007/978-1-4613-9940-7_3.CrossRefGoogle Scholar
Cai, J. F., Candès, E. J. and Shen, Z., “A singular value thresholding algorithm for matrix completion”, SIAM J. Optim. 20 (2010) 717–772; doi:10.1137/080738970.CrossRefGoogle Scholar
Candès, E. J. and Recht, B., “Exact matrix completion via convex optimization”, Found. Comput. Math. 9 (2009) 717–772; doi:10.1007/s10208-009-9045-5.CrossRefGoogle Scholar
Chen, Y. and Ye, X., “Projection onto a simplex”, arXiv:1101.6081v2, 2011.Google Scholar
Dattorro, J., Convex optimization and Euclidean distance geometry (Meboo Publishing, California, 2013).Google Scholar
Drineas, P., Javed, A., Magdon-Ismail, M., Pandurangant, G., Virrankoski, R. and Savvides, A., “Distance matrix reconstruction from incomplete distance information for sensor network localization”, Proc. IEEE Int. Conf. Sensor, Mesh and Ad Hoc Communications and Networks (SECON’06), 2006, 536–544; doi:10.1109/SAHCN.2006.288510.CrossRefGoogle Scholar
Escalante, R. and Raydan, M., Alternating Projection Methods (SIAM, Philadelphia, 2011) ;doi:10.1137/19781611971941.CrossRefGoogle Scholar
Fabry-Asztalos, L., Lorentz, I. and Andonie, R., “Molecular distance geometry optimization using geometric build-up and evolutionary techniques on GPU”, Comput. Intell. Bioinform. Comput. Biol. (2012) 321–328; doi:10.1109/CIBCB.2012.6217247.Google Scholar
Gaffke, N. and Mathar, R., “A cyclic projection algorithm via duality”, Metrika 36 (1989) 29–54 ;doi:10.1007/BF02614077.CrossRefGoogle Scholar
Gholami, M. R., Tetruashvili, L., Strm, E. G. and Censor, Y., “Cooperative wireless sensor network positioning via implicit convex feasibility”, IEEE Trans. Signal Process. 61 (2013) 5830–5840 ;doi:10.1109/TSP.2013.2279770.CrossRefGoogle Scholar
Glunt, W., Hayden, T. L., Hong, S. and Wells, J., “An alternating projection algorithm for computing the nearest Euclidean distance matrix”, SIAM J. Matrix Anal. Appl. 11 (1990) 589–600 ;doi:10.1137/0611042.CrossRefGoogle Scholar
Hayden, T. L. and Wells, J., “Approximation by matrices positive semidefinite on a subspace”, Linear Algebra Appl. 109 (1988) 115–130; doi:10.1016/0024-3795(88)90202-9.CrossRefGoogle Scholar
Hesse, R. and Luke, D. R., “Nonconvex notions of regularity and convergence of fundamental algorithms for feasibility problems”, SIAM J. Optim. 23 (2013) 2397–2419 ;doi:10.1137/120902653.CrossRefGoogle Scholar
Higham, N. J., “Computing the polar decomposition—with applications”, SIAM J. Sci. Stat. Comput. 7 (1986) 1160–1174; doi:10.1137/0907079.CrossRefGoogle Scholar
Hjørungnes, A., Complex-Valued Matrix Derivatives: with Applications in Signal Processing and Communications (Cambridge University Press, New York, 2011) ;doi:10.1017/CBO9780511921490.CrossRefGoogle Scholar
Horadam, K. J., Hadamard Matrices and their Applications (Princeton University Press, New Jersey, 2007).CrossRefGoogle Scholar
Horn, R. A. and Johnson, C. R., Matrix Analysis (Cambridge University Press, New York, 1985) ;doi:101017/CBO9780511810817.CrossRefGoogle Scholar
Johnson, C. R., “Matrix completion problems: a survey”, Proc. Sympos. Appl. Math. 40 (1990) 171–198; doi:10.1090/psapm/040/1059486.CrossRefGoogle Scholar
Kirslock, N. and Wolkowicz, H., “Explicit sensor network localization using semidefinite representations and facial reductions”, SIAM J. Optim. 20 (2010) 2679–2708.CrossRefGoogle Scholar
Koukouvinos, C. and Stylianou, S., “On skew-Hadamard matrices”, Discrete Math. 309 (2008) 2723–2731; doi:10.1016/j.disc.2006.06.037.CrossRefGoogle Scholar
Laurent, M., “Matrix completion problems”, Encyclopedia Optim. 271 (2001) 221–229 ;doi:10.1007/0-306-48332-7_271.Google Scholar
Leung, K. H. and Schmidt, B., “New restrictions on possible order of circulant Hadamard matrices”, Des. Codes Cryptogr. 64 (2012) 143–151; doi:10.1007/s10623-011-9493-1.CrossRefGoogle Scholar
McKay, B. D., “Hadamard equivalence via graph isomorphism”, Discrete Math. 27 (1979) 213–214; doi:10.1016/0012-365X(79)90113-4.CrossRefGoogle Scholar
Piantadosi, J., Howlett, P. and Borwein, J. M., “Modelling and simulation of seasonal rainfall using the principle of maximum entropy”, Entropy 16 (2014) 747–769; doi:10.3390/e16020747.Google Scholar
Schoenberg, I. J., “Remarks to Maurice Fréchet’s article ‘Sur la définition axiomatique d’une classe d’espace distanciés vectoriellement applicable sur l’espace de Hilbert’”, Ann. of Math. (2) 36 (1935) 724–732.CrossRefGoogle Scholar
Schönemann, P. H., “A generalized solution to the orthogonal Procrustes problem”, Psychometrika 31 (1966) 1–10; doi:10.1007/BF02289451.CrossRefGoogle Scholar
Takouda, P. L., “Un probléme d’approximation matricielle: quelle est la matrice bistochastique la plus proche d’une matrice donnée?”, RAIRO Oper. Res. 39 (2005) 35–54.CrossRefGoogle Scholar
Yuen, A. K., Lafon, O., Charpentier, O. T., Roy, M., Brunet, F., Berthault, P., Sakellariou, D., Robert, B., Rimsky, S., Pillon, F., Cintrat, J. C. and Rousseau, B., “Measurement of long-range interatomic distances by solid-state tritium-NMR spectroscopy”, J. Amer. Chem. Soc. 132 (2010) 1734–1735; doi:10.1021/ja908915v.CrossRefGoogle ScholarPubMed