November  2016, 10(4): 1149-1180. doi: 10.3934/ipi.2016036

A minimal surface criterion for graph partitioning

1. 

Montana State University, Department of Mathematical Sciences, 2-214 Wilson Hall, Box 172400, Bozeman, MT 59717-2400, United States

2. 

University of Utah, Salt Lake City, Department of Mathematics, 155 S. 1400 E, Rm 233, Salt Lake City, UT 84112, United States

Received  July 2015 Revised  May 2016 Published  October 2016

We consider a geometric approach to graph partitioning based on the graph Beltrami energy, a discrete version of a functional that appears in classical minimal surface problems. More specifically, the optimality criterion is given by the sum of the minimal Beltrami energies of the partition components. Since the Beltrami energy interpolates between the Total Variation and Dirichlet energies, various results for optimal partitions for these two energies can be recovered. We adapt primal-dual convex optimization methods to solve for the minimal Beltrami energy for each component of a given partition. A rearrangement algorithm is proposed to find the graph partition to minimize a relaxed version of the objective. The method is applied to several clustering problems on graphs constructed from manifold discretizations, synthetic data, the MNIST handwritten digit dataset, and image segmentation. The model has a semisupervised extension and provides a natural representative for the clusters as well.
Citation: Dominique Zosso, Braxton Osting. A minimal surface criterion for graph partitioning. Inverse Problems and Imaging, 2016, 10 (4) : 1149-1180. doi: 10.3934/ipi.2016036
References:
[1]

K. J. Arrow, L. Hurwicz and H. Uzawa, Studies in Linear and Non-Linear Programming, Cambridge Univ. Press, 1958.

[2]

I. Babuska, The finite element method with penalty, Mathematics of Computation, 27 (1973), 221-228. doi: 10.1090/S0025-5718-1973-0351118-5.

[3]

D. A. Bader, H. Meyerhenke, P. Sanders and D. Wagner (eds.), Graph Partitioning and Graph Clustering, American Mathematical Society, 2013. doi: 10.1090/conm/588.

[4]

D. Barash, Fundamental relationship between bilateral filtering, adaptive smoothing, and the nonlinear diffusion equation, IEEE Transactions on Pattern Analysis and Machine Intelligence, 24 (2002), 844-847. doi: 10.1109/TPAMI.2002.1008390.

[5]

B. Bogosel, Shape Optimization and Spectral Problems, Ph.D. thesis, Chambéry, 2015.

[6]

B. Bogosel, Partitions minimizing an anisotropic length,, 2016., (). 

[7]

V. Bonnaillie-Noël and B. Helffer, Numerical analysis of nodal sets for eigenvalues of Aharonov-Bohm Hamiltonians on the square with application to minimal partitions, Experimental Mathematics, 20 (2011), 304-322. doi: 10.1080/10586458.2011.565240.

[8]

V. Bonnaillie-Noël, B. Helffer and G. Vial, Numerical simulations for nodal domains and spectral minimal partitions, ESAIM: Control, Optimisation and Calculus of Variations, 16 (2010), 221-246. doi: 10.1051/cocv:2008074.

[9]

V. Bonnaillie-Noël and C. Léna, Spectral minimal partitions for a family of tori,, URL , (). 

[10]

B. Bourdin, D. Bucur and É. Oudet, Optimal partitions for eigenvalues, SIAM Journal on Scientific Computing, 31 (2010), 4100-4114. doi: 10.1137/090747087.

[11]

T. Brox and D. Cremers, On local region models and a statistical interpretation of the piecewise smooth Mumford-Shah functional, International Journal of Computer Vision, 84 (2009), 184-193. doi: 10.1007/s11263-008-0153-5.

[12]

D. Bucur, G. Butazzo and A. Henrot, Existence results for some optimal partition problems, Adv. Math. Sci. Appl., 8 (1998), 571-579.

[13]

D. Bucur and G. Butazzo, Variational Methods in Shape Optimization Problems, vol. 65 of Progress in Nonlinear Differential Equations and Their Applications, Birkhäuser Boston, 2005.

[14]

D. Bucur and B. Velichkov, Multiphase shape optimization problems, SIAM Journal on Control and Optimization, 52 (2014), 3556-3591. doi: 10.1137/130917272.

[15]

L. A. Cafferelli and F. H. Lin, An optimal partition problem for eigenvalues, Journal of Scientific Computing, 31 (2007), 5-18. doi: 10.1007/s10915-006-9114-8.

[16]

A. Chambolle and T. Pock, A first-order primal-dual algorithm for convex problems with applications to imaging, Journal of Mathematical Imaging and Vision, 40 (2011), 120-145. doi: 10.1007/s10851-010-0251-1.

[17]

T. F. Chan and L. A. Vese, Active contours without edges, IEEE Transactions on Image Processing, 10 (2001), 266-277. doi: 10.1109/83.902291.

[18]

H. Cohn and A. Kumar, Universally optimal distribution of points on spheres, Journal of the American Mathematical Society, 20 (2007), 99-148. doi: 10.1090/S0894-0347-06-00546-7.

[19]

O. Cybulski, V. Babin and R. Holyst, Minimization of the Renyi entropy production in the space-partitioning process, Physical Review E, 71 (2005), 046130, 10pp. doi: 10.1103/PhysRevE.71.046130.

[20]

O. Cybulski and R. Holyst, Three-dimensional space partition based on the first Laplacian eigenvalues in cells, Physical Review E, 77 (2008), 056101, 8pp. doi: 10.1103/PhysRevE.77.056101.

[21]

L. Dascal, G. Rosman and R. Kimmel, Efficient Beltrami filtering of color images via vector extrapolation, in SSVM'07: Proceedings of the 1st international conference on Scale space and variational methods in computer vision, Springer-Verlag, 4485 (2007), 92-103. doi: 10.1007/978-3-540-72823-8_9.

[22]

A. P. Dempster, N. M. Laird and D. B. Rubin, Maximum likelihood from incomplete data via the EM algorithm, Journal of the Royal Statistical Society. Series B (Methodological), 39 (1977), 1-38.

[23]

J. Duchi, S. Shalev-Shwartz, Y. Singer and T. Chandra, Efficient projections onto the l1-ball for learning in high dimensions, in Proceedings of the 25th international conference on Machine learning - ICML '08, ACM Press, New York, New York, USA, 2008, 272-279.

[24]

I. Ekeland and R. Temam, Convex Analysis and Variational Problems, North-Holland Publishing Company, Amsterdam, 1976.

[25]

S. Esedoglu and F. Otto, Threshold dynamics for networks with arbitrary surface tensions, Communications on Pure and Applied Mathematics, 68 (2015), 808-864. doi: 10.1002/cpa.21527.

[26]

E. Esser, X. Zhang and T. F. Chan, A general framework for a class of first order primal-dual algorithms for convex optimization in imaging science, SIAM Journal on Imaging Sciences, 3 (2010), 1015-1046. doi: 10.1137/09076934X.

[27]

M. Feigin and N. Sochen, Anisotropic regularization for inverse problems with application to the Wiener filter with Gaussian and impulse noise, in Scale Space and Variational Methods in Computer Vision, vol. 5567 of Lecture Notes in Computer Science, Springer Berlin / Heidelberg, 2009, 319-330. doi: 10.1007/978-3-642-02256-2_27.

[28]

R. Gabbrielli, A new counter-example to Kelvin's conjecture on minimal surfaces, Philosophical Magazine Letters, 89 (2009), 483-491. doi: 10.1080/09500830903022651.

[29]

C. Garcia-Cardona, E. Merkurjev, A. L. Bertozzi, A. Flenner and A. G. Percus, Multiclass data segmentation using diffuse interface methods on graphs, IEEE Transactions on Pattern Analysis and Machine Intelligence, 36 (2014), 1600-1613. doi: 10.1109/TPAMI.2014.2300478.

[30]

E. Giusti, Minimal Surfaces and Functions of Bounded Variation, Springer Science & Business Media, 1984. doi: 10.1007/978-1-4684-9486-0.

[31]

T. C. Hales, The honeycomb conjecture, Discrete & Computational Geometry, 25 (2001), 1-22. doi: 10.1007/s004540010071.

[32]

B. Helffer, On spectral minimal partitions: A survey, Milan J. Math., 78 (2010), 575-590. doi: 10.1007/s00032-010-0129-0.

[33]

B. Helffer and T. Hoffmann-Ostenhof, Remarks on two notions of spectral minimal partitions, Adv. Math. Sci. Appl., 20 (2010), 249-263.

[34]

B. Helffer, T. Hoffmann-Ostenhof and S. Terracini, On spectral minimal partitions: The case of the sphere, 2010, Around the research of Vladimir Maz'ya. III, Int. Math. Ser. (N. Y.), Springer, New York, 13 (2010), 153-178. doi: 10.1007/978-1-4419-1345-6_6.

[35]

C. Herring, Some theorems on the free energies of crystal surfaces, Physical Review, 82 (1951), 87-93. doi: 10.1103/PhysRev.82.87.

[36]

R. Kaftory, N. A. Sochen and Y. Y. Zeevi, Variational blind deconvolution of multi-channel images, Int. J. Imaging Syst. Technol., 15 (2005), 56-63. doi: 10.1002/ima.20038.

[37]

R. Kimmel, R. Malladi and N. Sochen, Images as embedded maps and minimal surfaces: Movies, color, texture, and volumetric medical images, Int. J. Comput. Vis., 39 (2000), 111-129.

[38]

C. Li, C.-Y. Kao, J. C. Gore and Z. Ding, Minimization of region-scalable fitting energy for image segmentation, IEEE Transactions on Image Processing, 17 (2008), 1940-1949. doi: 10.1109/TIP.2008.2002304.

[39]

Z. Liang and Y. Li, Beltrami flow in Hilbert space with applications to image denoising, Journal of Electronic Imaging, 21 (2012), 043019, 1-11. doi: 10.1117/1.JEI.21.4.043019.

[40]

S. Lloyd, Least squares quantization in PCM, IEEE Transactions on Information Theory, 28 (1982), 129-137. doi: 10.1109/TIT.1982.1056489.

[41]

L. Lopez-Perez, R. Deriche and N. Sochen, The Beltrami flow over triangulated manifolds, in CVAMIA and MMBIA Workshop at ECCV 2004, 3117 (2004), 135-144. doi: 10.1007/978-3-540-27816-0_12.

[42]

E. Merkurjev, T. Kostic and A. L. Bertozzi, An MBO scheme on graphs for segmentation and image processing, SIAM J. Imaging Sciences, 6 (2013), 1903-1930. doi: 10.1137/120886935.

[43]

B. Merriman, J. K. Bence and S. Osher, Diffusion Generated Motion by Mean Curvature, Technical report, UCLA CAM Report 92-18, 1992.

[44]

B. Merriman, J. K. Bence and S. Osher, Diffusion generated motion by mean curvature,, AMS Selected Letters, (): 73. 

[45]

B. Osting and C. D. White, Nonnegative matrix factorization of transition matrices via eigenvalue optimization, in NIPS OPT, 2013.

[46]

B. Osting, C. D. White and É. Oudet, Minimal Dirichlet energy partitions for graphs, SIAM Journal on Scientific Computing, 36 (2014), A1635-A1651. doi: 10.1137/130934568.

[47]

É. Oudet, Approximation of partitions of least perimeter by $\Gamma$-convergence: around Kelvin's conjecture, Experimental Mathematics, 20 (2011), 260-270. doi: 10.1080/10586458.2011.565233.

[48]

J. Plateau, Statique Expérimentale et Théorique des Liquides Soumis Aux Seules Forces Moléculaires, Gauthier-Villars, Paris, 1873.

[49]

G. Pólya and G. Szegő, Isoperimetric inequalities in mathematical physics, Princeton University Press, 1951.

[50]

G. Rosman, X.-C. Tai, L. Dascal and R. Kimmel, Polyakov action for efficient color image processing, Trends and Topics in Computer Vision, the series Lecture Notes in Computer Science, 6554 (2010), 50-61. doi: 10.1007/978-3-642-35740-4_5.

[51]

A. Roussos and P. Maragos, Tensor-based image diffusions derived from generalizations of the total variation and Beltrami functionals, in 2010 IEEE International Conference on Image Processing, IEEE, 2010, 4141-4144. doi: 10.1109/ICIP.2010.5653241.

[52]

L. Rudin, S. Osher and E. Fatemi, Nonlinear total variation based noise removal algorithms, Physica D, 60 (1992), 259-268. doi: 10.1016/0167-2789(92)90242-F.

[53]

C. Sagiv, N. A. Sochen and Y. Y. Zeevi, Gabor feature space diffusion via the minimal weighted area method, in Energy Minimization Methods in Computer Vision and Pattern Recognition, 2134 (2001), 621-635. doi: 10.1007/3-540-44745-8_41.

[54]

H. Schaeffer and L. Vese, Variational dynamics of free triple junctions, Journal of Scientific Computing, 59 (2014), 386-411. doi: 10.1007/s10915-013-9767-z.

[55]

H. A. Schwarz, Gesammelte mathematische Abhandlungen, Springer Berlin Heidelberg, Berlin, Heidelberg, 1890. doi: 10.1007/978-3-642-50665-9.

[56]

W. Sir Thomson, On the division of space with minimum partitional area, Acta Mathematica, 11 (1887), 121-134. doi: 10.1007/BF02612322.

[57]

N. Sochen, R. Deriche and L. Lopez-Perez, The Beltrami flow over implicit manifolds, in 9th IEEE ICCV, 2003, 832-839. doi: 10.1109/ICCV.2003.1238434.

[58]

N. Sochen, R. Kimmel and R. Malladi, A general framework for low level vision, IEEE Transactions on Image Processing, 7 (1998), 310-318. doi: 10.1109/83.661181.

[59]

N. A. Sochen, Stochastic processes in vision: From Langevin to Beltrami, Proceedings Eighth IEEE International Conference on Computer Vision. ICCV 2001, 1 (2001), 288-293. doi: 10.1109/ICCV.2001.937531.

[60]

A. Spira, R. Kimmel and N. Sochen, A short-time Beltrami kernel for smoothing images and manifolds, IEEE Transactions on Image Processing, 16 (2007), 1628-1636. doi: 10.1109/TIP.2007.894253.

[61]

M. van den Berg and D. Bucur, On the torsion function with Robin or Dirichlet boundary conditions, Journal of Functional Analysis, 266 (2014), 1647-1666. doi: 10.1016/j.jfa.2013.07.007.

[62]

Y. van Gennip, N. Guillen, B. Osting and A. L. Bertozzi, Mean curvature, threshold dynamics, and phase field theory on finite graphs, Milan Journal of Mathematics, 82 (2014), 3-65. doi: 10.1007/s00032-014-0216-8.

[63]

A. Wetzler and R. Kimmel, Efficient Beltrami flow in patch-space, in Scale Space and Variational Methods in Computer Vision 2011 (eds. A. M. Bruckstein, B. M. Haar Romeny, A. M. Bronstein and M. M. Bronstein), vol. 6667 of Lecture Notes in Computer Science, Springer Berlin Heidelberg, Berlin, Heidelberg, 2012, 134-143. doi: 10.1007/978-3-642-24785-9_12.

[64]

Z. Yang, T. Hao, O. Dikmen, X. Chen and E. Oja, Clustering by nonnegative matrix factorization using graph random walk, in Advances in Neural Information Processing Systems 25, 2012, 1079-1087.

[65]

M. Zhu and T. Chan, An Efficient Primal-Dual Hybrid Gradient Algorithm for Total Variation Image Restoration, Technical report, UCLA CAM Report 08-34, 2008.

[66]

M. Zhu, S. J. Wright and T. F. Chan, Duality-based algorithms for total-variation-regularized image restoration, Computational Optimization and Applications, 47 (2010), 377-400. doi: 10.1007/s10589-008-9225-2.

[67]

D. Zosso, J. An, J. Stevick, N. Takaki, M. Weiss, L. S. Slaughter, H. H. Cao, P. S. Weiss and A. L. Bertozzi, Image segmentation with dynamic artifacts detection and bias correction,, submitted to: AIMS J. Inverse Problems and Imaging, (). 

[68]

D. Zosso and A. Bustin, A Primal-Dual Projected Gradient Algorithm for Efficient Beltrami Regularization, Technical report, UCLA CAM Report 14-52, 2014.

show all references

References:
[1]

K. J. Arrow, L. Hurwicz and H. Uzawa, Studies in Linear and Non-Linear Programming, Cambridge Univ. Press, 1958.

[2]

I. Babuska, The finite element method with penalty, Mathematics of Computation, 27 (1973), 221-228. doi: 10.1090/S0025-5718-1973-0351118-5.

[3]

D. A. Bader, H. Meyerhenke, P. Sanders and D. Wagner (eds.), Graph Partitioning and Graph Clustering, American Mathematical Society, 2013. doi: 10.1090/conm/588.

[4]

D. Barash, Fundamental relationship between bilateral filtering, adaptive smoothing, and the nonlinear diffusion equation, IEEE Transactions on Pattern Analysis and Machine Intelligence, 24 (2002), 844-847. doi: 10.1109/TPAMI.2002.1008390.

[5]

B. Bogosel, Shape Optimization and Spectral Problems, Ph.D. thesis, Chambéry, 2015.

[6]

B. Bogosel, Partitions minimizing an anisotropic length,, 2016., (). 

[7]

V. Bonnaillie-Noël and B. Helffer, Numerical analysis of nodal sets for eigenvalues of Aharonov-Bohm Hamiltonians on the square with application to minimal partitions, Experimental Mathematics, 20 (2011), 304-322. doi: 10.1080/10586458.2011.565240.

[8]

V. Bonnaillie-Noël, B. Helffer and G. Vial, Numerical simulations for nodal domains and spectral minimal partitions, ESAIM: Control, Optimisation and Calculus of Variations, 16 (2010), 221-246. doi: 10.1051/cocv:2008074.

[9]

V. Bonnaillie-Noël and C. Léna, Spectral minimal partitions for a family of tori,, URL , (). 

[10]

B. Bourdin, D. Bucur and É. Oudet, Optimal partitions for eigenvalues, SIAM Journal on Scientific Computing, 31 (2010), 4100-4114. doi: 10.1137/090747087.

[11]

T. Brox and D. Cremers, On local region models and a statistical interpretation of the piecewise smooth Mumford-Shah functional, International Journal of Computer Vision, 84 (2009), 184-193. doi: 10.1007/s11263-008-0153-5.

[12]

D. Bucur, G. Butazzo and A. Henrot, Existence results for some optimal partition problems, Adv. Math. Sci. Appl., 8 (1998), 571-579.

[13]

D. Bucur and G. Butazzo, Variational Methods in Shape Optimization Problems, vol. 65 of Progress in Nonlinear Differential Equations and Their Applications, Birkhäuser Boston, 2005.

[14]

D. Bucur and B. Velichkov, Multiphase shape optimization problems, SIAM Journal on Control and Optimization, 52 (2014), 3556-3591. doi: 10.1137/130917272.

[15]

L. A. Cafferelli and F. H. Lin, An optimal partition problem for eigenvalues, Journal of Scientific Computing, 31 (2007), 5-18. doi: 10.1007/s10915-006-9114-8.

[16]

A. Chambolle and T. Pock, A first-order primal-dual algorithm for convex problems with applications to imaging, Journal of Mathematical Imaging and Vision, 40 (2011), 120-145. doi: 10.1007/s10851-010-0251-1.

[17]

T. F. Chan and L. A. Vese, Active contours without edges, IEEE Transactions on Image Processing, 10 (2001), 266-277. doi: 10.1109/83.902291.

[18]

H. Cohn and A. Kumar, Universally optimal distribution of points on spheres, Journal of the American Mathematical Society, 20 (2007), 99-148. doi: 10.1090/S0894-0347-06-00546-7.

[19]

O. Cybulski, V. Babin and R. Holyst, Minimization of the Renyi entropy production in the space-partitioning process, Physical Review E, 71 (2005), 046130, 10pp. doi: 10.1103/PhysRevE.71.046130.

[20]

O. Cybulski and R. Holyst, Three-dimensional space partition based on the first Laplacian eigenvalues in cells, Physical Review E, 77 (2008), 056101, 8pp. doi: 10.1103/PhysRevE.77.056101.

[21]

L. Dascal, G. Rosman and R. Kimmel, Efficient Beltrami filtering of color images via vector extrapolation, in SSVM'07: Proceedings of the 1st international conference on Scale space and variational methods in computer vision, Springer-Verlag, 4485 (2007), 92-103. doi: 10.1007/978-3-540-72823-8_9.

[22]

A. P. Dempster, N. M. Laird and D. B. Rubin, Maximum likelihood from incomplete data via the EM algorithm, Journal of the Royal Statistical Society. Series B (Methodological), 39 (1977), 1-38.

[23]

J. Duchi, S. Shalev-Shwartz, Y. Singer and T. Chandra, Efficient projections onto the l1-ball for learning in high dimensions, in Proceedings of the 25th international conference on Machine learning - ICML '08, ACM Press, New York, New York, USA, 2008, 272-279.

[24]

I. Ekeland and R. Temam, Convex Analysis and Variational Problems, North-Holland Publishing Company, Amsterdam, 1976.

[25]

S. Esedoglu and F. Otto, Threshold dynamics for networks with arbitrary surface tensions, Communications on Pure and Applied Mathematics, 68 (2015), 808-864. doi: 10.1002/cpa.21527.

[26]

E. Esser, X. Zhang and T. F. Chan, A general framework for a class of first order primal-dual algorithms for convex optimization in imaging science, SIAM Journal on Imaging Sciences, 3 (2010), 1015-1046. doi: 10.1137/09076934X.

[27]

M. Feigin and N. Sochen, Anisotropic regularization for inverse problems with application to the Wiener filter with Gaussian and impulse noise, in Scale Space and Variational Methods in Computer Vision, vol. 5567 of Lecture Notes in Computer Science, Springer Berlin / Heidelberg, 2009, 319-330. doi: 10.1007/978-3-642-02256-2_27.

[28]

R. Gabbrielli, A new counter-example to Kelvin's conjecture on minimal surfaces, Philosophical Magazine Letters, 89 (2009), 483-491. doi: 10.1080/09500830903022651.

[29]

C. Garcia-Cardona, E. Merkurjev, A. L. Bertozzi, A. Flenner and A. G. Percus, Multiclass data segmentation using diffuse interface methods on graphs, IEEE Transactions on Pattern Analysis and Machine Intelligence, 36 (2014), 1600-1613. doi: 10.1109/TPAMI.2014.2300478.

[30]

E. Giusti, Minimal Surfaces and Functions of Bounded Variation, Springer Science & Business Media, 1984. doi: 10.1007/978-1-4684-9486-0.

[31]

T. C. Hales, The honeycomb conjecture, Discrete & Computational Geometry, 25 (2001), 1-22. doi: 10.1007/s004540010071.

[32]

B. Helffer, On spectral minimal partitions: A survey, Milan J. Math., 78 (2010), 575-590. doi: 10.1007/s00032-010-0129-0.

[33]

B. Helffer and T. Hoffmann-Ostenhof, Remarks on two notions of spectral minimal partitions, Adv. Math. Sci. Appl., 20 (2010), 249-263.

[34]

B. Helffer, T. Hoffmann-Ostenhof and S. Terracini, On spectral minimal partitions: The case of the sphere, 2010, Around the research of Vladimir Maz'ya. III, Int. Math. Ser. (N. Y.), Springer, New York, 13 (2010), 153-178. doi: 10.1007/978-1-4419-1345-6_6.

[35]

C. Herring, Some theorems on the free energies of crystal surfaces, Physical Review, 82 (1951), 87-93. doi: 10.1103/PhysRev.82.87.

[36]

R. Kaftory, N. A. Sochen and Y. Y. Zeevi, Variational blind deconvolution of multi-channel images, Int. J. Imaging Syst. Technol., 15 (2005), 56-63. doi: 10.1002/ima.20038.

[37]

R. Kimmel, R. Malladi and N. Sochen, Images as embedded maps and minimal surfaces: Movies, color, texture, and volumetric medical images, Int. J. Comput. Vis., 39 (2000), 111-129.

[38]

C. Li, C.-Y. Kao, J. C. Gore and Z. Ding, Minimization of region-scalable fitting energy for image segmentation, IEEE Transactions on Image Processing, 17 (2008), 1940-1949. doi: 10.1109/TIP.2008.2002304.

[39]

Z. Liang and Y. Li, Beltrami flow in Hilbert space with applications to image denoising, Journal of Electronic Imaging, 21 (2012), 043019, 1-11. doi: 10.1117/1.JEI.21.4.043019.

[40]

S. Lloyd, Least squares quantization in PCM, IEEE Transactions on Information Theory, 28 (1982), 129-137. doi: 10.1109/TIT.1982.1056489.

[41]

L. Lopez-Perez, R. Deriche and N. Sochen, The Beltrami flow over triangulated manifolds, in CVAMIA and MMBIA Workshop at ECCV 2004, 3117 (2004), 135-144. doi: 10.1007/978-3-540-27816-0_12.

[42]

E. Merkurjev, T. Kostic and A. L. Bertozzi, An MBO scheme on graphs for segmentation and image processing, SIAM J. Imaging Sciences, 6 (2013), 1903-1930. doi: 10.1137/120886935.

[43]

B. Merriman, J. K. Bence and S. Osher, Diffusion Generated Motion by Mean Curvature, Technical report, UCLA CAM Report 92-18, 1992.

[44]

B. Merriman, J. K. Bence and S. Osher, Diffusion generated motion by mean curvature,, AMS Selected Letters, (): 73. 

[45]

B. Osting and C. D. White, Nonnegative matrix factorization of transition matrices via eigenvalue optimization, in NIPS OPT, 2013.

[46]

B. Osting, C. D. White and É. Oudet, Minimal Dirichlet energy partitions for graphs, SIAM Journal on Scientific Computing, 36 (2014), A1635-A1651. doi: 10.1137/130934568.

[47]

É. Oudet, Approximation of partitions of least perimeter by $\Gamma$-convergence: around Kelvin's conjecture, Experimental Mathematics, 20 (2011), 260-270. doi: 10.1080/10586458.2011.565233.

[48]

J. Plateau, Statique Expérimentale et Théorique des Liquides Soumis Aux Seules Forces Moléculaires, Gauthier-Villars, Paris, 1873.

[49]

G. Pólya and G. Szegő, Isoperimetric inequalities in mathematical physics, Princeton University Press, 1951.

[50]

G. Rosman, X.-C. Tai, L. Dascal and R. Kimmel, Polyakov action for efficient color image processing, Trends and Topics in Computer Vision, the series Lecture Notes in Computer Science, 6554 (2010), 50-61. doi: 10.1007/978-3-642-35740-4_5.

[51]

A. Roussos and P. Maragos, Tensor-based image diffusions derived from generalizations of the total variation and Beltrami functionals, in 2010 IEEE International Conference on Image Processing, IEEE, 2010, 4141-4144. doi: 10.1109/ICIP.2010.5653241.

[52]

L. Rudin, S. Osher and E. Fatemi, Nonlinear total variation based noise removal algorithms, Physica D, 60 (1992), 259-268. doi: 10.1016/0167-2789(92)90242-F.

[53]

C. Sagiv, N. A. Sochen and Y. Y. Zeevi, Gabor feature space diffusion via the minimal weighted area method, in Energy Minimization Methods in Computer Vision and Pattern Recognition, 2134 (2001), 621-635. doi: 10.1007/3-540-44745-8_41.

[54]

H. Schaeffer and L. Vese, Variational dynamics of free triple junctions, Journal of Scientific Computing, 59 (2014), 386-411. doi: 10.1007/s10915-013-9767-z.

[55]

H. A. Schwarz, Gesammelte mathematische Abhandlungen, Springer Berlin Heidelberg, Berlin, Heidelberg, 1890. doi: 10.1007/978-3-642-50665-9.

[56]

W. Sir Thomson, On the division of space with minimum partitional area, Acta Mathematica, 11 (1887), 121-134. doi: 10.1007/BF02612322.

[57]

N. Sochen, R. Deriche and L. Lopez-Perez, The Beltrami flow over implicit manifolds, in 9th IEEE ICCV, 2003, 832-839. doi: 10.1109/ICCV.2003.1238434.

[58]

N. Sochen, R. Kimmel and R. Malladi, A general framework for low level vision, IEEE Transactions on Image Processing, 7 (1998), 310-318. doi: 10.1109/83.661181.

[59]

N. A. Sochen, Stochastic processes in vision: From Langevin to Beltrami, Proceedings Eighth IEEE International Conference on Computer Vision. ICCV 2001, 1 (2001), 288-293. doi: 10.1109/ICCV.2001.937531.

[60]

A. Spira, R. Kimmel and N. Sochen, A short-time Beltrami kernel for smoothing images and manifolds, IEEE Transactions on Image Processing, 16 (2007), 1628-1636. doi: 10.1109/TIP.2007.894253.

[61]

M. van den Berg and D. Bucur, On the torsion function with Robin or Dirichlet boundary conditions, Journal of Functional Analysis, 266 (2014), 1647-1666. doi: 10.1016/j.jfa.2013.07.007.

[62]

Y. van Gennip, N. Guillen, B. Osting and A. L. Bertozzi, Mean curvature, threshold dynamics, and phase field theory on finite graphs, Milan Journal of Mathematics, 82 (2014), 3-65. doi: 10.1007/s00032-014-0216-8.

[63]

A. Wetzler and R. Kimmel, Efficient Beltrami flow in patch-space, in Scale Space and Variational Methods in Computer Vision 2011 (eds. A. M. Bruckstein, B. M. Haar Romeny, A. M. Bronstein and M. M. Bronstein), vol. 6667 of Lecture Notes in Computer Science, Springer Berlin Heidelberg, Berlin, Heidelberg, 2012, 134-143. doi: 10.1007/978-3-642-24785-9_12.

[64]

Z. Yang, T. Hao, O. Dikmen, X. Chen and E. Oja, Clustering by nonnegative matrix factorization using graph random walk, in Advances in Neural Information Processing Systems 25, 2012, 1079-1087.

[65]

M. Zhu and T. Chan, An Efficient Primal-Dual Hybrid Gradient Algorithm for Total Variation Image Restoration, Technical report, UCLA CAM Report 08-34, 2008.

[66]

M. Zhu, S. J. Wright and T. F. Chan, Duality-based algorithms for total-variation-regularized image restoration, Computational Optimization and Applications, 47 (2010), 377-400. doi: 10.1007/s10589-008-9225-2.

[67]

D. Zosso, J. An, J. Stevick, N. Takaki, M. Weiss, L. S. Slaughter, H. H. Cao, P. S. Weiss and A. L. Bertozzi, Image segmentation with dynamic artifacts detection and bias correction,, submitted to: AIMS J. Inverse Problems and Imaging, (). 

[68]

D. Zosso and A. Bustin, A Primal-Dual Projected Gradient Algorithm for Efficient Beltrami Regularization, Technical report, UCLA CAM Report 14-52, 2014.

[1]

Yanqin Bai, Xuerui Gao, Guoqiang Wang. Primal-dual interior-point algorithms for convex quadratic circular cone optimization. Numerical Algebra, Control and Optimization, 2015, 5 (2) : 211-231. doi: 10.3934/naco.2015.5.211

[2]

Xiaojing Ye, Haomin Zhou. Fast total variation wavelet inpainting via approximated primal-dual hybrid gradient algorithm. Inverse Problems and Imaging, 2013, 7 (3) : 1031-1050. doi: 10.3934/ipi.2013.7.1031

[3]

Yu-Hong Dai, Zhouhong Wang, Fengmin Xu. A Primal-dual algorithm for unfolding neutron energy spectrum from multiple activation foils. Journal of Industrial and Management Optimization, 2021, 17 (5) : 2367-2387. doi: 10.3934/jimo.2020073

[4]

Siqi Li, Weiyi Qian. Analysis of complexity of primal-dual interior-point algorithms based on a new kernel function for linear optimization. Numerical Algebra, Control and Optimization, 2015, 5 (1) : 37-46. doi: 10.3934/naco.2015.5.37

[5]

Gianni Di Pillo, Giampaolo Liuzzi, Stefano Lucidi. A primal-dual algorithm for nonlinear programming exploiting negative curvature directions. Numerical Algebra, Control and Optimization, 2011, 1 (3) : 509-528. doi: 10.3934/naco.2011.1.509

[6]

Kai Wang, Deren Han. On the linear convergence of the general first order primal-dual algorithm. Journal of Industrial and Management Optimization, 2021  doi: 10.3934/jimo.2021134

[7]

Guoqiang Wang, Zhongchen Wu, Zhongtuan Zheng, Xinzhong Cai. Complexity analysis of primal-dual interior-point methods for semidefinite optimization based on a parametric kernel function with a trigonometric barrier term. Numerical Algebra, Control and Optimization, 2015, 5 (2) : 101-113. doi: 10.3934/naco.2015.5.101

[8]

Xiayang Zhang, Yuqian Kong, Shanshan Liu, Yuan Shen. A relaxed parameter condition for the primal-dual hybrid gradient method for saddle-point problem. Journal of Industrial and Management Optimization, 2022  doi: 10.3934/jimo.2022008

[9]

Dan Li, Li-Ping Pang, Fang-Fang Guo, Zun-Quan Xia. An alternating linearization method with inexact data for bilevel nonsmooth convex optimization. Journal of Industrial and Management Optimization, 2014, 10 (3) : 859-869. doi: 10.3934/jimo.2014.10.859

[10]

Paul B. Hermanns, Nguyen Van Thoai. Global optimization algorithm for solving bilevel programming problems with quadratic lower levels. Journal of Industrial and Management Optimization, 2010, 6 (1) : 177-196. doi: 10.3934/jimo.2010.6.177

[11]

Adil Bagirov, Sona Taheri, Soodabeh Asadi. A difference of convex optimization algorithm for piecewise linear regression. Journal of Industrial and Management Optimization, 2019, 15 (2) : 909-932. doi: 10.3934/jimo.2018077

[12]

Yong Wang, Wanquan Liu, Guanglu Zhou. An efficient algorithm for non-convex sparse optimization. Journal of Industrial and Management Optimization, 2019, 15 (4) : 2009-2021. doi: 10.3934/jimo.2018134

[13]

Jen-Yen Lin, Hui-Ju Chen, Ruey-Lin Sheu. Augmented Lagrange primal-dual approach for generalized fractional programming problems. Journal of Industrial and Management Optimization, 2013, 9 (4) : 723-741. doi: 10.3934/jimo.2013.9.723

[14]

Mohamed A. Tawhid, Ahmed F. Ali. An effective hybrid firefly algorithm with the cuckoo search for engineering optimization problems. Mathematical Foundations of Computing, 2018, 1 (4) : 349-368. doi: 10.3934/mfc.2018017

[15]

Jin-Zan Liu, Xin-Wei Liu. A dual Bregman proximal gradient method for relatively-strongly convex optimization. Numerical Algebra, Control and Optimization, 2021  doi: 10.3934/naco.2021028

[16]

Lipu Zhang, Yinghong Xu, Zhengjing Jin. An efficient algorithm for convex quadratic semi-definite optimization. Numerical Algebra, Control and Optimization, 2012, 2 (1) : 129-144. doi: 10.3934/naco.2012.2.129

[17]

Fengmin Wang, Dachuan Xu, Donglei Du, Chenchen Wu. Primal-dual approximation algorithms for submodular cost set cover problems with linear/submodular penalties. Numerical Algebra, Control and Optimization, 2015, 5 (2) : 91-100. doi: 10.3934/naco.2015.5.91

[18]

Yu-Hong Dai, Xin-Wei Liu, Jie Sun. A primal-dual interior-point method capable of rapidly detecting infeasibility for nonlinear programs. Journal of Industrial and Management Optimization, 2020, 16 (2) : 1009-1035. doi: 10.3934/jimo.2018190

[19]

Yixuan Yang, Yuchao Tang, Meng Wen, Tieyong Zeng. Preconditioned Douglas-Rachford type primal-dual method for solving composite monotone inclusion problems with applications. Inverse Problems and Imaging, 2021, 15 (4) : 787-825. doi: 10.3934/ipi.2021014

[20]

Yibing Lv, Zhongping Wan. Linear bilevel multiobjective optimization problem: Penalty approach. Journal of Industrial and Management Optimization, 2019, 15 (3) : 1213-1223. doi: 10.3934/jimo.2018092

2020 Impact Factor: 1.639

Metrics

  • PDF downloads (258)
  • HTML views (0)
  • Cited by (6)

Other articles
by authors

[Back to Top]