Matrix-free convex optimization modeling. (English) Zbl 1354.90092
Goldengorin, Boris (ed.), Optimization and applications in control and data sciences. In honor of Boris T. Polyak’s 80th birthday. Selected papers based on the presentations at the international conference, Moscow, Russia, May, 13–15, 2015. Cham: Springer (ISBN 978-3-319-42054-7/hbk; 978-3-319-42056-1/ebook). Springer Optimization and Its Applications 115, 221-264 (2016).
Summary: We introduce a convex optimization modeling framework that transforms a convex optimization problem expressed in a form natural and convenient for the user into an equivalent cone program in a way that preserves fast linear transforms in the original problem. By representing linear functions in the transformation process not as matrices, but as graphs that encode composition of linear operators, we arrive at a matrix-free cone program, i.e., one whose data matrix is represented by a linear operator and its adjoint. This cone program can then be solved by a matrix-free cone solver. By combining the matrix-free modeling framework and cone solver, we obtain a general method for efficiently solving convex optimization problems involving fast linear transforms.
For the entire collection see [Zbl 1356.93004].
For the entire collection see [Zbl 1356.93004].
MSC:
| 90C25 | Convex programming |
Software:
PDCO; SDPT3; Caffe; DSDP5; SPGL1; YALMIP; SDPA; Torch; PENSDP; SeDuMi; CVXOPT; Theano; Mosek; CVX; CSparse; ECOS; DiffSharp; TensorFlow; CVXPY; GitHub; POGS; TFOCS; CVXGEN; SCS; Convex.jl; Halide; LSMRReferences:
| [1] | Abadi, M., Agarwal, A., Barham, P., Brevdo, E., Chen, Z., Citro, C., Corrado, G., Davis, A., Dean, J., Devin, M., Ghemawat, S., Goodfellow, I., Harp, A., Irving, G., Isard, M., Jia, Y., Jozefowicz, R., Kaiser, L., Kudlur, M., Levenberg, J., Mané, D., Monga, R., Moore, S., Murray, D., Olah, C., Schuster, M., Shlens, J., Steiner, B., Sutskever, I., Talwar, K., Tucker, P., Vanhoucke, V., Vasudevan, V., Viégas, F., Vinyals, O., Warden, P., Wattenberg, M., Wicke, M., Yu, Y., Zheng, X.: TensorFlow: large-scale machine learning on heterogeneous systems. (2015) http://tensorflow.org/ . Cited 2 March 2016 |
| [2] | Ahmed, N., Natarajan, T., Rao, K.: Discrete cosine transform. IEEE Trans. Comput. C-23 (1), 90–93 (1974) · Zbl 0273.65097 · doi:10.1109/T-C.1974.223784 |
| [3] | Aho, A., Lam, M., Sethi, R., Ullman, J.: Compilers: Principles, Techniques, and Tools, 2nd edn. Addison-Wesley Longman, Boston (2006) · Zbl 1155.68020 |
| [4] | Akle, S.: Algorithms for unsymmetric cone optimization and an implementation for problems with the exponential cone. Ph.D. thesis, Stanford University (2015) |
| [5] | Andersen, M., Dahl, J., Liu, Z., Vandenberghe, L.: Interior-point methods for large-scale cone programming. In: Sra, S., Nowozin, S., Wright, S. (eds.) Optimization for Machine Learning, pp. 55–83. MIT Press, Cambridge (2012) |
| [6] | Andersen, M., Dahl, J., Vandenberghe, L.: CVXOPT: Python software for convex optimization, version 1.1 (2015). http://cvxopt.org/ . Cited 2 March 2016 |
| [7] | Bastien, F., Lamblin, P., Pascanu, R., Bergstra, J., Goodfellow, I., Bergeron, A., Bouchard, N., Bengio, Y.: Theano: new features and speed improvements. In: Deep Learning and Unsupervised Feature Learning, Neural Information Processing Systems Workshop (2012) |
| [8] | Baydin, A., Pearlmutter, B., Radul, A., Siskind, J.: Automatic differentiation in machine learning: a survey. Preprint (2015). http://arxiv.org/abs/1502.05767 . Cited 2 March 2016 · Zbl 06982909 |
| [9] | Beck, A., Teboulle, M.: Fast gradient-based algorithms for constrained total variation image denoising and deblurring problems. IEEE Trans. Image Process. 18 (11), 2419–2434 (2009) · Zbl 1371.94049 · doi:10.1109/TIP.2009.2028250 |
| [10] | Beck, A., Teboulle, M.: A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM J. Imag. Sci. 2 (1), 183–202 (2009) · Zbl 1175.94009 · doi:10.1137/080716542 |
| [11] | Becker, S., Candès, E., Grant, M.: Templates for convex cone problems with applications to sparse signal recovery. Math. Program. Comput. 3 (3), 165–218 (2011) · Zbl 1257.90042 · doi:10.1007/s12532-011-0029-5 |
| [12] | Benson, S., Ye, Y.: Algorithm 875: DSDP5–software for semidefinite programming. ACM Trans. Math. Software 34 (3), (2008) · Zbl 1291.65173 · doi:10.1145/1356052.1356057 |
| [13] | Bergstra, J., Breuleux, O., Bastien, F., Lamblin, P., Pascanu, R., Desjardins, G., Turian, J., Warde-Farley, D., Bengio, Y.: Theano: a CPU and GPU math expression compiler. In: Proceedings of the Python for Scientific Computing Conference (2010) |
| [14] | Börm, S., Grasedyck, L., Hackbusch, W.: Introduction to hierarchical matrices with applications. Eng. Anal. Bound. Elem. 27 (5), 405–422 (2003) · Zbl 1035.65042 · doi:10.1016/S0955-7997(02)00152-2 |
| [15] | Boyd, S., Parikh, N., Chu, E., Peleato, B., Eckstein, J.: Distributed optimization and statistical learning via the alternating direction method of multipliers. Found. Trends Mach. Learn. 3, 1–122 (2011) · Zbl 1229.90122 · doi:10.1561/2200000016 |
| [16] | Boyd, S., Vandenberghe, L.: Convex Optimization. Cambridge University Press, Cambridge (2004) · Zbl 1058.90049 · doi:10.1017/CBO9780511804441 |
| [17] | Bracewell, R.: The fast Hartley transform. In: Proceedings of the IEEE, vol. 72, pp. 1010–1018 (1984) |
| [18] | Brandt, A., McCormick, S., Ruge, J.: Algebraic multigrid (AMG) for sparse matrix equations. In: D. Evans (ed.) Sparsity and its Applications, pp. 257–284. Cambridge University Press, Cambridge (1985) · Zbl 0548.65014 |
| [19] | Brélaz, D.: New methods to color the vertices of a graph. Commun. ACM 22 (4), 251–256 (1979) · Zbl 0394.05022 · doi:10.1145/359094.359101 |
| [20] | Candès, E., Demanet, L., Donoho, D., Ying, L.: Fast discrete curvelet transforms. Multiscale Model. Simul. 5 (3), 861–899 (2006) · Zbl 1122.65134 · doi:10.1137/05064182X |
| [21] | Carrier, J., Greengard, L., Rokhlin, V.: A fast adaptive multipole algorithm for particle simulations. SIAM J. Sci. Stat. Comput. 9 (4), 669–686 (1988) · Zbl 0656.65004 · doi:10.1137/0909044 |
| [22] | Chambolle, A., Pock, T.: A first-order primal-dual algorithm for convex problems with applications to imaging. J. Math. Imaging Vision 40 (1), 120–145 (2011) · Zbl 1255.68217 · doi:10.1007/s10851-010-0251-1 |
| [23] | Chan, T., Esedoglu, S., Nikolova, M.: Algorithms for finding global minimizers of image segmentation and denoising models. SIAM J. Appl. Math. 66 (5), 1632–1648 (2006) · Zbl 1117.94002 · doi:10.1137/040615286 |
| [24] | Chen, S., Donoho, D., Saunders, M.: Atomic decomposition by basis pursuit. SIAM J. Sci. Comput. 20 (1), 33–61 (1998) · Zbl 0919.94002 · doi:10.1137/S1064827596304010 |
| [25] | Choi, C., Ye, Y.: Solving sparse semidefinite programs using the dual scaling algorithm with an iterative solver. Working paper, Department of Management Sciences, University of Iowa (2000) |
| [26] | Chu, E., O’Donoghue, B., Parikh, N., Boyd, S.: A primal-dual operator splitting method for conic optimization. Preprint (2013). http://stanford.edu/ boyd/papers/pdf/pdos.pdf . Cited 2 March 2016 |
| [27] | Chu, E., Parikh, N., Domahidi, A., Boyd, S.: Code generation for embedded second-order cone programming. In: Proceedings of the European Control Conference, pp. 1547–1552 (2013) |
| [28] | Cohen, A., Daubechies, I., Feauveau, J.C.: Biorthogonal bases of compactly supported wavelets. Commun. Pure Appl. Math. 45 (5), 485–560 (1992) · Zbl 0776.42020 · doi:10.1002/cpa.3160450502 |
| [29] | Collobert, R., Kavukcuoglu, K., Farabet, C.: Torch7: a MATLAB-like environment for machine learning. In: BigLearn, Neural Information Processing Systems Workshop (2011) |
| [30] | Cooley, J., Lewis, P., Welch, P.: The fast Fourier transform and its applications. IEEE Trans. Educ. 12 (1), 27–34 (1969) · doi:10.1109/TE.1969.4320436 |
| [31] | Cooley, J., Tukey, J.: An algorithm for the machine calculation of complex Fourier series. Math. Comput. 19 (90), 297–301 (1965) · Zbl 0127.09002 · doi:10.1090/S0025-5718-1965-0178586-1 |
| [32] | Daubechies, I.: Orthonormal bases of compactly supported wavelets. Commun. Pure Appl. Math. 41 (7), 909–996 (1988) · Zbl 0644.42026 · doi:10.1002/cpa.3160410705 |
| [33] | Daubechies, I.: Ten lectures on wavelets. SIAM, Philadelphia (1992) · Zbl 0776.42018 · doi:10.1137/1.9781611970104 |
| [34] | Davis, T.: Direct Methods for Sparse Linear Systems (Fundamentals of Algorithms 2). SIAM, Philadelphia (2006) · Zbl 1119.65021 · doi:10.1137/1.9780898718881 |
| [35] | Diamond, S., Boyd, S.: Convex optimization with abstract linear operators. In: Proceedings of the IEEE International Conference on Computer Vision, pp. 675–683 (2015) · doi:10.1109/ICCV.2015.84 |
| [36] | 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 |
| [37] | Diamond, S., Boyd, S.: Stochastic matrix-free equilibration. J. Optim. Theory Appl. (2016, to appear) · Zbl 1367.65068 · doi:10.1007/s10957-016-0990-2 |
| [38] | Do, M., Vetterli, M.: The finite ridgelet transform for image representation. IEEE Trans. Image Process. 12 (1), 16–28 (2003) · Zbl 1283.94011 · doi:10.1109/TIP.2002.806252 |
| [39] | Domahidi, A., Chu, E., Boyd, S.: ECOS: an SOCP solver for embedded systems. In: Proceedings of the European Control Conference, pp. 3071–3076 (2013) |
| [40] | Dudgeon, D., Mersereau, R.: Multidimensional Digital Signal Processing. Prentice-Hall, Englewood Cliffs (1984) · Zbl 0643.94001 |
| [41] | Duff, I., Erisman, A., Reid, J.: Direct Methods for Sparse Matrices. Oxford University Press, New York (1986) · Zbl 0604.65011 |
| [42] | Figueiredo, M., Nowak, R., Wright, S.: Gradient projection for sparse reconstruction: application to compressed sensing and other inverse problems. IEEE J. Sel. Top. Signal Process. 1 (4), 586–597 (2007) · doi:10.1109/JSTSP.2007.910281 |
| [43] | Fong, D., Saunders, M.: LSMR: an iterative algorithm for sparse least-squares problems. SIAM J. Sci. Comput. 33 (5), 2950–2971 (2011) · Zbl 1232.65052 · doi:10.1137/10079687X |
| [44] | Forsyth, D., Ponce, J.: Computer Vision: A Modern Approach. Prentice Hall, Upper Saddle River (2002) |
| [45] | Fougner, C., Boyd, S.: Parameter selection and pre-conditioning for a graph form solver. (2015, preprint). http://arxiv.org/pdf/1503.08366v1.pdf . Cited 2 March 2016 |
| [46] | Fountoulakis, K., Gondzio, J., Zhlobich, P.: Matrix-free interior point method for compressed sensing problems. Math. Program. Comput. 6 (1), 1–31 (2013) · Zbl 1304.90137 · doi:10.1007/s12532-013-0063-6 |
| [47] | Fujisawa, K., Fukuda, M., Kobayashi, K., Kojima, M., Nakata, K., Nakata, M., Yamashita, M.: SDPA (semidefinite programming algorithm) user’s manual – version 7.0.5. Tech. rep. (2008) |
| [48] | Fukuda, M., Kojima, M., Shida, M.: Lagrangian dual interior-point methods for semidefinite programs. SIAM J. Optim. 12 (4), 1007–1031 (2002) · Zbl 1035.90054 · doi:10.1137/S1052623401387349 |
| [49] | Gardiner, J., Laub, A., Amato, J., Moler, C.: Solution of the Sylvester matrix equation AXB T + CXD T =E. ACM Trans. Math. Software 18 (2), 223–231 (1992) · Zbl 0893.65026 · doi:10.1145/146847.146929 |
| [50] | Gilbert, A., Strauss, M., Tropp, J., Vershynin, R.: One sketch for all: fast algorithms for compressed sensing. In: Proceedings of the ACM Symposium on Theory of Computing, pp. 237–246 (2007) · Zbl 1232.94008 · doi:10.1145/1250790.1250824 |
| [51] | Goldstein, T., Osher, S.: The split Bregman method for 1-regularized problems. SIAM J. Imag. Sci. 2 (2), 323–343 (2009) · Zbl 1177.65088 · doi:10.1137/080725891 |
| [52] | Gondzio, J.: Matrix-free interior point method. Comput. Optim. Appl. 51 (2), 457–480 (2012) · Zbl 1241.90179 · doi:10.1007/s10589-010-9361-3 |
| [53] | Gondzio, J.: Convergence analysis of an inexact feasible interior point method for convex quadratic programming. SIAM J. Optim. 23 (3), 1510–1527 (2013) · Zbl 1286.65075 · doi:10.1137/120886017 |
| [54] | Gondzio, J., Grothey, A.: Parallel interior-point solver for structured quadratic programs: application to financial planning problems. Ann. Oper. Res. 152 (1), 319–339 (2007) · Zbl 1144.90510 · doi:10.1007/s10479-006-0139-z |
| [55] | Grant, M.: Disciplined convex programming. Ph.D. thesis, Stanford University (2004) · Zbl 1130.90382 |
| [56] | Grant, M., Boyd, S.: Graph implementations for nonsmooth convex programs. In: Blondel, V., Boyd, S., Kimura, H. (eds.) Recent Advances in Learning and Control. Lecture Notes in Control and Information Sciences, pp. 95–110. Springer, London (2008) · Zbl 1205.90223 |
| [57] | Grant, M., Boyd, S.: CVX: MATLAB software for disciplined convex programming, version 2.1 (2014). http://cvxr.com/cvx . Cited 2 March 2016 |
| [58] | Grant, M., Boyd, S., Ye, Y.: Disciplined convex programming. In: Liberti, L., Maculan, N. (eds.) Global Optimization: From Theory to Implementation, Nonconvex Optimization and its Applications, pp. 155–210. Springer, New York (2006) · Zbl 1130.90382 · doi:10.1007/0-387-30528-9_7 |
| [59] | Greengard, L., Rokhlin, V.: A fast algorithm for particle simulations. J. Comput. Phys. 73 (2), 325–348 (1987) · Zbl 0629.65005 · doi:10.1016/0021-9991(87)90140-9 |
| [60] | Greengard, L., Strain, J.: The fast Gauss transform. SIAM J. Sci. Stat. Comput. 12 (1), 79–94 (1991) · Zbl 0721.65089 · doi:10.1137/0912004 |
| [61] | Griewank, A.: On automatic differentiation. In: Iri, M., Tanabe, K. (eds.) Mathematical Programming: Recent Developments and Applications, pp. 83–108. Kluwer Academic, Tokyo (1989) · Zbl 0696.65015 |
| [62] | Hackbusch, W.: Multi-Grid Methods and Applications. Springer, Heidelberg (1985) · Zbl 0595.65106 · doi:10.1007/978-3-662-02427-0 |
| [63] | Hackbusch, W.: A sparse matrix arithmetic based on \[ \mathcal{H} \] -matrices. Part I: introduction to \[ \mathcal{H} \] -matrices. Computing 62 (2), 89–108 (1999) · Zbl 0927.65063 · doi:10.1007/s006070050015 |
| [64] | Hackbusch, W., Khoromskij, B., Sauter, S.: On 2 \[ \mathcal{H}^{2} \] -matrices. In: Bungartz, H.J., Hoppe, R., Zenger, C. (eds.) Lectures on Applied Mathematics, pp. 9–29. Springer, Heidelberg (2000) · Zbl 0963.65043 · doi:10.1007/978-3-642-59709-1_2 |
| [65] | Halldórsson, M.: A still better performance guarantee for approximate graph coloring. Inf. Process. Lett. 45 (1), 19–23 (1993) · Zbl 0768.68043 · doi:10.1016/0020-0190(93)90246-6 |
| [66] | Hennenfent, G., Herrmann, F., Saab, R., Yilmaz, O., Pajean, C.: SPOT: a linear operator toolbox, version 1.2 (2014). http://www.cs.ubc.ca/labs/scl/spot/index.html . Cited 2 March 2016 |
| [67] | Hestenes, M., Stiefel, E.: Methods of conjugate gradients for solving linear systems. J. Res. Nat. Bur. Stand. 49 (6), 409–436 (1952) · Zbl 0048.09901 · doi:10.6028/jres.049.044 |
| [68] | Hien, L.: Differential properties of Euclidean projection onto power cone. Math. Methods Oper. Res. 82 (3), 265–284 (2015) · Zbl 1342.90183 · doi:10.1007/s00186-015-0514-0 |
| [69] | Jacques, L., Duval, L., Chaux, C., Peyré, G.: A panorama on multiscale geometric representations, intertwining spatial, directional and frequency selectivity. IEEE Trans. Signal Process. 91 (12), 2699–2730 (2011) |
| [70] | Jensen, A., la Cour-Harbo, A.: Ripples in Mathematics. Springer, Berlin (2001) · Zbl 0989.42013 · doi:10.1007/978-3-642-56702-5 |
| [71] | Jia, Y., Shelhamer, E., Donahue, J., Karayev, S., Long, J., Girshick, R., Guadarrama, S., Darrell, T.: Caffe: Convolutional architecture for fast feature embedding. (2014, preprint). http://arxiv.org/abs/1408.5093 . Cited 2 March 2016 |
| [72] | Karp, R.: Reducibility among combinatorial problems. In: Miller, R., Thatcher, J., Bohlinger, J. (eds.) Complexity of Computer Computations, The IBM Research Symposia Series, pp. 85–103. Springer, New York (1972) · doi:10.1007/978-1-4684-2001-2_9 |
| [73] | Kelner, J., Orecchia, L., Sidford, A., Zhu, A.: A simple, combinatorial algorithm for solving SDD systems in nearly-linear time. In: Proceedings of the ACM Symposium on Theory of Computing, pp. 911–920 (2013) · Zbl 1293.68145 · doi:10.1145/2488608.2488724 |
| [74] | Kim, S.J., Koh, K., Lustig, M., Boyd, S., Gorinevsky, D.: An interior-point method for large-scale 1-regularized least squares. IEEE J. Sel. Top. Signal Process. 1 (4), 606–617 (2007) · doi:10.1109/JSTSP.2007.910971 |
| [75] | Kočvara, M., Stingl, M.: On the solution of large-scale SDP problems by the modified barrier method using iterative solvers. Math. Program. 120 (1), 285–287 (2009) · Zbl 1177.90313 · doi:10.1007/s10107-008-0250-9 |
| [76] | Kovacevic, J., Vetterli, M.: Nonseparable multidimensional perfect reconstruction filter banks and wavelet bases for n \[ \mathcal{R}^{n} \] . IEEE Trans. Inf. Theory 38 (2), 533–555 (1992) · doi:10.1109/18.119722 |
| [77] | Krishnaprasad, P., Barakat, R.: A descent approach to a class of inverse problems. J. Comput. Phys. 24 (4), 339–347 (1977) · Zbl 0361.65102 · doi:10.1016/0021-9991(77)90026-2 |
| [78] | Lan, G., Lu, Z., Monteiro, R.: Primal-dual first-order methods with O(1{\(\epsilon\)}) iteration-complexity for cone programming. Math. Program. 126 (1), 1–29 (2011) · Zbl 1208.90113 · doi:10.1007/s10107-008-0261-6 |
| [79] | Liberty, E.: Simple and deterministic matrix sketching. In: Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 581–588 (2013) · doi:10.1145/2487575.2487623 |
| [80] | Lim, J.: Two-dimensional Signal and Image Processing. Prentice-Hall, Upper Saddle River (1990) |
| [81] | Lin, Y., Lee, D., Saul, L.: Nonnegative deconvolution for time of arrival estimation. In: Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing, vol. 2, pp. 377–380 (2004) |
| [82] | Loan, C.V.: Computational Frameworks for the Fast Fourier Transform. SIAM, Philadelphia (1992) · Zbl 0757.65154 · doi:10.1137/1.9781611970999 |
| [83] | Lofberg, J.: YALMIP: A toolbox for modeling and optimization in MATLAB. In: Proceedings of the IEEE International Symposium on Computed Aided Control Systems Design, pp. 294–289 (2004) · doi:10.1109/CACSD.2004.1393890 |
| [84] | Lu, Y., Do, M.: Multidimensional directional filter banks and surfacelets. IEEE Trans. Image Process. 16 (4), 918–931 (2007) · doi:10.1109/TIP.2007.891785 |
| [85] | Mallat, S.: A theory for multiresolution signal decomposition: the wavelet representation. IEEE Trans. Pattern Anal. Mach. Intell. 11 (7), 674–693 (1989) · Zbl 0709.94650 · doi:10.1109/34.192463 |
| [86] | Martucci, S.: Symmetric convolution and the discrete sine and cosine transforms. IEEE Trans. Signal Process. 42 (5), 1038–1051 (1994) · doi:10.1109/78.295213 |
| [87] | Mattingley, J., Boyd, S.: CVXGEN: A code generator for embedded convex optimization. Optim. Eng. 13 (1), 1–27 (2012) · Zbl 1293.65095 · doi:10.1007/s11081-011-9176-9 |
| [88] | Miller, J., Zhu, J., Quigley, P.: CVXcanon, version 0.0.22 (2015). https://github.com/cvxgrp/CVXcanon . Cited 2 March 2016 |
| [89] | MOSEK optimization software, version 7 (2015). https://mosek.com/ . Cited 2 March 2016 |
| [90] | Nesterov, Y.: Towards nonsymmetric conic optimization. Optim. Methods Software 27 (4–5), 893–917 (2012) · Zbl 1260.90129 · doi:10.1080/10556788.2011.567270 |
| [91] | Nesterov, Y., Nemirovskii, A.: Interior-Point Polynomial Algorithms in Convex Programming. SIAM, Philadelphia (1994) · Zbl 0824.90112 · doi:10.1137/1.9781611970791 |
| [92] | Nesterov, Y., Nemirovsky, A.: Conic formulation of a convex programming problem and duality. Optim. Methods Softw. 1 (2), 95–115 (1992) · doi:10.1080/10556789208805510 |
| [93] | Nocedal, J., Wright, S.: Numerical Optimization. Springer, New York (2006) · Zbl 1104.65059 |
| [94] | 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 |
| [95] | Parikh, N., Boyd, S.: Proximal algorithms. Found. Trends Optim. 1 (3), 123–231 (2014) |
| [96] | 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) · doi:10.1109/ICCV.2011.6126441 |
| [97] | 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) · doi:10.1109/ICCV.2009.5459348 |
| [98] | Ragan-Kelley, J., Barnes, C., Adams, A., Paris, S., Durand, F., Amarasinghe, S.: Halide: A language and compiler for optimizing parallelism, locality, and recomputation in image processing pipelines. In: Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation, pp. 519–530 (2013) · doi:10.1145/2491956.2462176 |
| [99] | Saunders, M., Kim, B., Maes, C., Akle, S., Zahr, M.: PDCO: Primal-dual interior method for convex objectives (2013). http://web.stanford.edu/group/SOL/software/pdco/ . Cited 2 March 2016 |
| [100] | Skajaa, A., Ye, Y.: A homogeneous interior-point algorithm for nonsymmetric convex conic optimization. Math. Program. 150 (2), 391–422 (2014) · Zbl 1309.90078 · doi:10.1007/s10107-014-0773-1 |
| [101] | Spielman, D., Teng, S.H.: Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems. In: Proceedings of the ACM Symposium on Theory of Computing, pp. 81–90 (2004) · Zbl 1192.65048 · doi:10.1145/1007352.1007372 |
| [102] | Starck, J.L., Candès, E., Donoho, D.: The curvelet transform for image denoising. IEEE Trans. Image Process. 11 (6), 670–684 (2002) · Zbl 1288.94011 · doi:10.1109/TIP.2002.1014998 |
| [103] | Sturm, J.: Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones. Optim. Methods Softw. 11 (1–4), 625–653 (1999) · Zbl 0973.90526 · doi:10.1080/10556789908805766 |
| [104] | Toh, K.C.: Solving large scale semidefinite programs via an iterative solver on the augmented systems. SIAM J. Optim. 14 (3), 670–698 (2004) · Zbl 1071.90026 · doi:10.1137/S1052623402419819 |
| [105] | Toh, K.C., Todd, M., Tütüncü, R.: SDPT3 – a MATLAB software package for semidefinite programming, version 4.0. Optim. Methods Softw. 11, 545–581 (1999) · Zbl 0997.90060 · doi:10.1080/10556789908805762 |
| [106] | Udell, M., Mohan, K., Zeng, D., Hong, J., Diamond, S., Boyd, S.: Convex optimization in Julia. In: Proceedings of the Workshop for High Performance Technical Computing in Dynamic Languages, pp. 18–28 (2014) · doi:10.1109/HPTCDL.2014.5 |
| [107] | Vaillant, G.: linop, version 0.7 (2013). http://pythonhosted.org//linop/ . Cited 2 March 2016 |
| [108] | van den Berg, E., Friedlander, M.: Probing the Pareto frontier for basis pursuit solutions. SIAM J. Sci. Comput. 31 (2), 890–912 (2009) · Zbl 1193.49033 · doi:10.1137/080714488 |
| [109] | Vandenberghe, L., Boyd, S.: A polynomial-time algorithm for determining quadratic Lyapunov functions for nonlinear systems. In: Proceedings of the European Conference on Circuit Theory and Design, pp. 1065–1068 (1993) |
| [110] | Vandenberghe, L., Boyd, S.: A primal-dual potential reduction method for problems involving matrix inequalities. Math. Program. 69 (1–3), 205–236 (1995) · Zbl 0857.90104 |
| [111] | Vishnoi, K.: Laplacian solvers and their algorithmic applications. Theor. Comput. Sci. 8 (1–2), 1–141 (2012) · Zbl 1280.65003 |
| [112] | Wright, S.: Primal-Dual Interior-Point Methods. SIAM, Philadelphia (1987) · Zbl 0863.65031 |
| [113] | Yang, C., Duraiswami, R., Davis, L.: Efficient kernel machines using the improved fast Gauss transform. In: Saul, L., Weiss, Y., Bottou, L. (eds.) Advances in Neural Information Processing Systems 17, pp. 1561–1568. MIT Press, Cambridge (2005) |
| [114] | Yang, C., Duraiswami, R., Gumerov, N., Davis, L.: Improved fast Gauss transform and efficient kernel density estimation. In: Proceedings of the IEEE International Conference on Computer Vision, vol. 1, pp. 664–671 (2003) |
| [115] | Ye, Y.: Interior Point Algorithms: Theory and Analysis. Wiley-Interscience, New York (2011) |
| [116] | Ying, L., Demanet, L., Candès, E.: 3D discrete curvelet transform. In: Proceedings of SPIE: Wavelets XI, vol. 5914, pp. 351–361 (2005) |
| [117] | Zach, C., Pock, T., Bischof, H.: A duality based approach for realtime TV- 1 optical flow. In: Hamprecht, F., Schnörr, C., Jähne, B. (eds.) Pattern Recognition. Lecture Notes in Computer Science, vol. 4713, pp. 214–223. Springer, Heidelberg (2007) |
| [118] | Zhao, X.Y., Sun, D., Toh, K.C.: A Newton-CG augmented Lagrangian method for semidefinite programming. SIAM J. Optim. 20 (4), 1737–1765 (2010) · Zbl 1213.90175 · doi:10.1137/080718206 |
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.
