×

Sparse approximation of fitting surface by elastic net. (English) Zbl 1453.65031

Summary: The goal of this paper is to develop a computational model and corresponding efficient algorithm for obtaining a sparse representation of the fitting surface to the given scattered data. The basic idea of the model is to utilize the principal shift invariant space and the balanced \(l_{1}, l_{2}\) norm minimization (named elastic net). The elastic net can be solved efficiently by an adapted split Bregman iteration algorithm. Numerical experiments indicate that by choosing appropriate regularization parameters, the model can efficiently provide an acceptable compromise between the minimization of the data mismatch term and the sparsity of the solution.

MSC:

65D05 Numerical interpolation
65D18 Numerical aspects of computer graphics, image analysis, and computational geometry
65F50 Computational methods for sparse matrices

Software:

lbdtik; ErresTools
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bauer, F; Lukas, M, Comparing parameter choice methods for regularization of ill-posed problem, Math Comput Simul, 81, 1795-1841, (2011) · Zbl 1220.65063 · doi:10.1016/j.matcom.2011.01.016
[2] Brezinski, C; Rodriguez, G; Seatzu, S, Error estimates for the regularization of least squares problems, Numer Algorithms, 51, 61-76, (2009) · Zbl 1166.65331 · doi:10.1007/s11075-008-9243-2
[3] Cai, J; Osher, S; Shen, Z, Split Bregman methods and frame based restoration, Multiscale Model Simul, 8, 337-369, (2009) · Zbl 1189.94014 · doi:10.1137/090753504
[4] Candès, EJ; Romberg, J; Tao, T, Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information, IEEE Trans Inform Theory, 52, 489-509, (2006) · Zbl 1231.94017 · doi:10.1109/TIT.2005.862083
[5] Candès, EJ; Romberg, J; Tao, T, Stable signal recovery from incomplete and inaccurate measurements, Commun Pure Appl Math, 59, 1207-1223, (2006) · Zbl 1098.94009 · doi:10.1002/cpa.20124
[6] Candès, EJ; Tao, T, Decoding by linear programming, IEEE Trans Inform Theory, 51, 4203-4215, (2005) · Zbl 1264.94121 · doi:10.1109/TIT.2005.858979
[7] Candès, EJ; Tao, T, Near-optimal signal recovery from random projections: universal encoding strategies, IEEE Trans Inform Theory, 52, 5406-5425, (2006) · Zbl 1309.94033 · doi:10.1109/TIT.2006.885507
[8] Castaño D, Kunoth A ((2003)) Adaptive fitting of scattered data by spline-wavelets. In: Curves and surfaces. Vanderbilt University Press, Nashville · Zbl 1036.65011
[9] Cohen, A; Dahmen, W; DeVore, R, Compressed sensing and best k-term approximation, J Am Math Soc, 22, 211-231, (2009) · Zbl 1206.94008 · doi:10.1090/S0894-0347-08-00610-3
[10] Dong, B; Shen, Z, Wavelet frame based surface reconstruction from unorganized points, J Comput Phys, 230, 8247-8255, (2011) · Zbl 1239.94007 · doi:10.1016/j.jcp.2011.07.022
[11] Donoho, D, De-noising by soft-thresholding, IEEE Trans Inform Theory, 41, 613-627, (1995) · Zbl 0820.62002 · doi:10.1109/18.382009
[12] Douglas, J; Rachford, HH, On the numerical solution of heat conduction problems in two and three space variables, Trans Am Math Soc, 82, 421-439, (1956) · Zbl 0070.35401 · doi:10.1090/S0002-9947-1956-0084194-4
[13] Eckstein J (1989) Splitting methods for monotone operators with applications to parallel optimization. Ph.D. Thesis, Massachusetts Institute of Technology, pp 964-979
[14] Efron, B; Hastie, T; Johnstone, I; Tibshirani, R, Least angle regression, Ann Stat, 32, 407-499, (2004) · Zbl 1091.62054 · doi:10.1214/009053604000000067
[15] Esser E (2009) Applications of lagrangian-based alternating direction methods and connections to split Bregman. Tech. rep, CAM report, UCLA
[16] Forsey, DR; Bartels, RH, Surface Fitting with hierarchical splines, ACM Trans Graph, 14, 134-161, (1995) · doi:10.1145/221659.221665
[17] Gabay, D; Mercier, B, A dual algorithm for the solution of nonlinear variational problems via finite element approximations, Comp Math Appl, 2, 17-40, (1976) · Zbl 0352.65034 · doi:10.1016/0898-1221(76)90003-1
[18] Goldstein, T; Osher, S, The split Bregman method for \(l_{1}\)-regularized problems, SIAM J Imaging Sci, 2, 323-343, (2009) · Zbl 1177.65088 · doi:10.1137/080725891
[19] Hastie, T; Zou, H, Regularization and variable selection with elastic net, J R Stat Soc B, 67, 301-320, (2005) · Zbl 1069.62054 · doi:10.1111/j.1467-9868.2005.00503.x
[20] Hochstenbacha, M; Reichel, L; Rodriguez, G, Regularization parameter determination for discrete ill-posed problems, J Comput Appl Math, 273, 132-149, (2015) · Zbl 1295.65046 · doi:10.1016/j.cam.2014.06.004
[21] Ji, H; Shen, Z; Xu, YH, Wavelet frame based scene reconstruction from range data, J Comput Phys, 229, 2093-2108, (2010) · Zbl 1185.65029 · doi:10.1016/j.jcp.2009.11.024
[22] Johnson, MJ; Shen, Z; Xu, YH, Scattered data reconstruction by regularization in B-spline and associated wavelet spaces, J Approx Theory, 159, 197-223, (2009) · Zbl 1181.41013 · doi:10.1016/j.jat.2009.02.005
[23] Kindermann, S, Convergence analysis of minimization-based noise-level-free parameter choice rules for ill-posed problems, Electron Trans Numer Anal, 38, 233-257, (2011) · Zbl 1287.65043
[24] Kunis, S; Rauhut, H, Random sampling of sparse trigonometric polynomials II-orthogonal matching pursuit versus basis pursuit, Found Comput Math, 8, 737-763, (2008) · Zbl 1165.94314 · doi:10.1007/s10208-007-9005-x
[25] Lee BG, Lee JJ, Kwon KR (2005) Quasi-interpolation based multilevel B-spline surface reconstruction from scattered data. Commun Sci Appl:1209-1218
[26] Lee, SY; Wolberg, G; Shin, SY, Scattered data interpolation with multilevel B-splines, IEEE Trans Vis Comput Graph, 3, 229-244, (1997) · doi:10.1109/2945.620490
[27] Lions, PL; Mercier, B, Splitting algorithms for the sum of two nonlinear operators, SIAM J Numer Anal, 16, 964-979, (1979) · Zbl 0426.65050 · doi:10.1137/0716071
[28] Bozzini, M; Rossini, M, Testing methods for 3D scattered data interpolation, Monogr Acad Cie Zaragoza, 20, 111-135, (2002) · Zbl 1036.65006
[29] Rauhut, H, Random sampling of sparse trigonometric polynomials, Appl Comput Harmon Anal, 22, 16-42, (2007) · Zbl 1123.94004 · doi:10.1016/j.acha.2006.05.002
[30] Rauhut, H, Stability results for random sampling of sparse trigonometric polynomials, IEEE Trans Inform Theory, 54, 5661-5670, (2008) · Zbl 1247.94010 · doi:10.1109/TIT.2008.2006382
[31] Regiska, T, A regularization parameter in discrete ill-posed problems, SIAM J Sci Comput, 17, 740c749, (1996) · Zbl 0865.65023
[32] Reichel, L; Rodriguez, G, Old and new parameter choice rules for discrete ill-posed problems, Numer Algorithms, 63, 65c87, (2013) · Zbl 1267.65045 · doi:10.1007/s11075-012-9612-8
[33] Reichel, L; Rodriguez, G; Seatzu, S, Error estimates for large-scale ill-posed problems, Numer Algorithms, 51, 341c361, (2009) · Zbl 1166.65332 · doi:10.1007/s11075-008-9244-1
[34] Schmitt, FJM; Barsky, BA; Du, WH, An adaptive subdivision method for surface Fitting from sampled data, Comput Graph, 20, 179-188, (1986) · doi:10.1145/15886.15906
[35] Setzer S (2009) Split (b)regman algorithm, douglas-rachfordsplitting and frame shrinkage. In: Proceedings of the second international conference on scale space methods and variational methods in computer vision
[36] Tibshirani, R, Regression shrinkage and selection via the lasso, J R Stat Soc Ser B, 58, 267-288, (1996) · Zbl 0850.62538
[37] Wang Z, Yu J, Xie X (2011) An improved algorithm for surface fitting based on B-spline function. Information and computing, pp 80-82 (2011 Fourth International Conference on)
[38] Yuan, M; Lin, Y, Model selection and estimation in regression with grouped variables, R Stat Soc, 68, 49-76, (2006) · Zbl 1141.62030 · doi:10.1111/j.1467-9868.2005.00532.x
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.