×

Stochastic matrix-free equilibration. (English) Zbl 1367.65068

Summary: We present a novel method for approximately equilibrating a matrix using only multiplication by the matrix and its transpose. Our method is based on convex optimization and projected stochastic gradient descent, using an unbiased estimate of a gradient obtained by a randomized method. Our method provably converges in expectation and empirically gets good results with a small number of iterations. We show how the method can be applied as a preconditioner for matrix-free iterative algorithms, substantially reducing the iterations required to reach a given level of precision. We also derive a novel connection between equilibration and condition number, showing that equilibration minimizes an upper bound on the condition number over all choices of row and column scalings.

MSC:

65F35 Numerical computation of matrix norms, conditioning, scaling
65K05 Numerical mathematical programming methods
90C15 Stochastic programming
90C25 Convex programming
65F08 Preconditioners for iterative methods

Software:

CVXPY; SCS; POGS; Gurobi; LSQR
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Hwang, I., Balakrishnan, H., Roy, K., Shin, J., Guibas, L., Tomlin, C.: Multiple-target tracking and identity management. In: Proceedings of IEEE Sensors, pp. 36-41 (2003) · Zbl 0718.62058
[2] Knight, P.: The Sinkhorn-Knopp algorithm: convergence and applications. SIAM J. Matrix Anal. Appl. 30(1), 261-275 (2008) · Zbl 1166.15301 · doi:10.1137/060659624
[3] Schneider, M., Zenios, S.: A comparative study of algorithms for matrix balancing. Oper. Res. 38(3), 439-455 (1990) · Zbl 0703.90094 · doi:10.1287/opre.38.3.439
[4] Bradley, A.: Algorithms for the equilibration of matrices and their application to limited-memory Quasi-Newton methods. Ph.D. thesis, Stanford University (2010) · Zbl 1342.90136
[5] Nocedal, J., Wright, S.: Numerical Optimization. Springer, New York (2000) · Zbl 0930.65067
[6] Takapoui, R., Javadi, H.: Preconditioning via diagonal scaling. EE364b: Convex Optimization II Class Project (2014). http://stanford.edu/class/ee364b/projects/2014projects/reports/takapoui_javadi_report.pdf
[7] Giselsson, P., Boyd, S.: Diagonal scaling in Douglas-Rachford splitting and ADMM. In: Proceedings of the IEEE Conference on Decision and Control, pp. 5033-5039 (2014) · Zbl 1330.49032
[8] Kelley, C.: Iterative Methods for Linear and Nonlinear Equations. Society for Industrial and Applied Mathematics, Philadelphia (1995) · Zbl 0832.65046 · doi:10.1137/1.9781611970944
[9] Greenbaum, A.: Iterative Methods for Solving Linear Systems. Society for Industrial and Applied Mathematics, Philadelphia (1997) · Zbl 0883.65022 · doi:10.1137/1.9781611970937
[10] Pock, T., Chambolle, A.: Diagonal preconditioning for first order primal-dual algorithms in convex optimization. In: Proceedings of the IEEE International Conference on Computer Vision, pp. 1762-1769 (2011) · Zbl 0048.09901
[11] Giselsson, P., Boyd, S.: Metric selection in fast dual forward-backward splitting. Automatica 62, 1-10 (2015) · Zbl 1330.49032 · doi:10.1016/j.automatica.2015.09.010
[12] Sluis, A.: Condition numbers and equilibration of matrices. Numer. Math. 14(1), 14-23 (1969) · Zbl 0182.48906 · doi:10.1007/BF02165096
[13] Sinkhorn, R., Knopp, P.: Concerning nonnegative matrices and doubly stochastic matrices. Pac. J. Math. 21(2), 343-348 (1967) · Zbl 0152.01403 · doi:10.2140/pjm.1967.21.343
[14] Ruiz, D.: A scaling algorithm to equilibrate both rows and columns norms in matrices. Technical report, Rutherford Appleton Lab., Oxon, UK, RAL-TR-2001-034 (2001)
[15] Hestenes, M., Stiefel, E.: Methods of conjugate gradients for solving linear systems. J. Res. Natl. Bur. Stand. 49(6), 409-436 (1952) · Zbl 0048.09901 · doi:10.6028/jres.049.044
[16] Paige, C., Saunders, M.: LSQR: an algorithm for sparse linear equations and sparse least squares. ACM Trans. Math. Softw. 8(1), 43-71 (1982) · Zbl 0478.65016 · doi:10.1145/355984.355989
[17] Chambolle, A., Pock, T.: A first-order primal-dual algorithm for convex problems with applications to imaging. J. Math. Imaging Vis. 40(1), 120-145 (2011) · Zbl 1255.68217 · doi:10.1007/s10851-010-0251-1
[18] Fougner, C., Boyd, S.: Parameter selection and pre-conditioning for a graph form solver. Preprint (2015). arXiv:1503.08366v1 · Zbl 1407.93126
[19] Balakrishnan, H., Hwang, I., Tomlin, C.: Polynomial approximation algorithms for belief matrix maintenance in identity management. In: Proceedings of the IEEE Conference on Decision and Control, pp. 4874-4879 (2004)
[20] Boyd, S., Vandenberghe, L.: Convex Optimization. Cambridge University Press, Cambridge (2004) · Zbl 1058.90049 · doi:10.1017/CBO9780511804441
[21] Corless, R., Gonnet, G., Hare, D., Jeffrey, D., Knuth, D.: On the Lambert \[WW\] function. Adv. Comput. Math. 5(1), 329-359 (1996) · Zbl 0863.65008 · doi:10.1007/BF02124750
[22] Hoorfar, A., Hassani, M.: Inequalities on the Lambert \[WW\] function and hyperpower function. J. Inequal. Pure Appl. Math. 9, 1-5 (2008) · Zbl 1163.33326
[23] Bekas, C., Kokiopoulou, E., Saad, Y.: An estimator for the diagonal of a matrix. Appl. Numer. Math. 57(11-12), 1214-1229 (2007) · Zbl 1123.65026 · doi:10.1016/j.apnum.2007.01.003
[24] Hutchinson, M.: A stochastic estimator of the trace of the influence matrix for Laplacian smoothing splines. Commun. Stat. Simul. Comput. 19(2), 433-450 (1990) · Zbl 0718.62058 · doi:10.1080/03610919008812866
[25] Lacoste-Julien, S., Schmidt, M., Bach, F.: A simpler approach to obtaining an \[{O}(1/t)O\](1/t) convergence rate for the projected stochastic subgradient method. Preprint (2002). arXiv:1212.2002v2
[26] Bubeck, S.: Convex optimization: algorithms and complexity. Found. Trends Mach. Learn. 8(3-4), 231-357 (2015) · Zbl 1365.90196 · doi:10.1561/2200000050
[27] Pock, T., Cremers, D., Bischof, H., Chambolle, A.: An algorithm for minimizing the Mumford-Shah functional. In: Proceedings of the IEEE International Conference on Computer Vision, pp. 1133-1140 (2009)
[28] Friedman, J., Hastie, T., Tibshirani, R.: The Elements of Statistical Learning, Springer Series in Statistics, vol. 1. Springer, New York (2001) · Zbl 0973.62007
[29] Diamond, S., Boyd, S.: CVXPY: a Python-embedded modeling language for convex optimization. J. Mach. Learn. Res. 17(83), 1-5 (2016) · Zbl 1360.90008
[30] Gurobi Optimization, Inc.: Gurobi optimizer reference manual (2015). http://www.gurobi.com · Zbl 1360.90008
[31] Lehoucq, R., Sorensen, D.: Deflation techniques for an implicitly restarted Arnoldi iteration. SIAM J. Matrix Anal. Appl. 17(4), 789-821 (1996) · Zbl 0863.65016 · doi:10.1137/S0895479895281484
[32] O’Donoghue, B., Chu, E., Parikh, N., Boyd, S.: Conic optimization via operator splitting and homogeneous self-dual embedding. J. Optim. Theory Appl. 169(3), 1042-1068 (2016) · Zbl 1342.90136 · doi:10.1007/s10957-016-0892-3
[33] Diamond, S., Boyd, S.: Convex optimization with abstract linear operators. In: Proceedings of the IEEE International Conference on Computer Vision, pp. 675-683 (2015)
[34] Diamond, S., Boyd, S.: Matrix-free convex optimization modeling. In: Goldengorin, B. (ed.) Optimization and Applications in Control and Data Sciences, Springer Optimization and Its Applications, vol. 115. Springer (2016, to appear) · Zbl 1354.90092
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.