American Institute of Mathematical Sciences

Advanced
August  2012, 6(3): 447-464. doi: 10.3934/ipi.2012.6.447

Optimal estimation of $\ell_1$-regularization prior from a regularized empirical Bayesian risk standpoint

Hui Huang 1, , Eldad Haber 2, and  Lior Horesh 3,

1. 

Shenzhen Key Lab of Visual Computing and Visual Analytics, Shenzhen Institute of Advanced Technology, Shenzhen, Guangdong, 518055, China
2. 

Department of Mathematics and Earth and Ocean Science, The University of British Columbia, Vancouver, BC, V6T 1Z2, Canada
3. 

Business Analytics and Mathematical Sciences, IBM T J Watson Research Center, Yorktown Heights, NY, 10598, United States

Received  March 2011 Revised  April 2012 Published  September 2012

We address the problem of prior matrix estimation for the solution of $\ell_1$-regularized ill-posed inverse problems. From a Bayesian viewpoint, we show that such a matrix can be regarded as an influence matrix in a multivariate $\ell_1$-Laplace density function. Assuming a training set is given, the prior matrix design problem is cast as a maximum likelihood term with an additional sparsity-inducing term. This formulation results in an unconstrained yet nonconvex optimization problem. Memory requirements as well as computation of the nonlinear, nonsmooth sub-gradient equations are prohibitive for large-scale problems. Thus, we introduce an iterative algorithm to design efficient priors for such large problems. We further demonstrate that the solutions of ill-posed inverse problems by incorporation of $\ell_1$-regularization using the learned prior matrix perform generally better than commonly used regularization techniques where the prior matrix is chosen a-priori.
Keywords: empirical Bayesian estimation, nonlinear and nonsmooth optimization., optimal design, $\ell_1$-regularization prior matrix.
Mathematics Subject Classification: Primary: 49N45; Secondary: 62F1.
Citation: Hui Huang, Eldad Haber, Lior Horesh. Optimal estimation of $\ell_1$-regularization prior from a regularized empirical Bayesian risk standpoint. Inverse Problems & Imaging, 2012, 6 (3) : 447-464. doi: 10.3934/ipi.2012.6.447
References:
[1]

IEEE Trans. Auto. Cont., 19 (1974), 716-723. doi: 10.1109/TAC.1974.1100705.  Google Scholar

[2]

IEEE Trans. Auto. Cont., 56 (2011), 2898-2911. doi: 10.1109/TAC.2011.2141430.  Google Scholar

[3]

SIAM J. Scient. Comput., 28 (2006), 339-358. doi: 10.1137/040617261.  Google Scholar

[4]

M2AN, Math. Model. Numer. Anal., 43 (2009), 689-708.  Google Scholar

[5]

Proc. IEEE Intl. Conf. on Acous., Spee., and Sig. Proc., 2000. Google Scholar

[6]

SIAM Review, 51 (2009), 34-81. doi: 10.1137/060657704.  Google Scholar

[7]

E. J. Candès and D. L. Donoho, "Curvelets: A Surprisingly Effective Nonadaptive Representation for Objects with Edges,", 1999., ().   Google Scholar

[8]

IEEE In Sig. Proc. Magaz., 25 (2008), 21-30. doi: 10.1109/MSP.2007.914731.  Google Scholar

[9]

SIAM, 2005.  Google Scholar

[10]

SIAM J. Imaging Sci., 3 (2010), 765-790. doi: 10.1137/080740167.  Google Scholar

[11]

SIAM Review, 41 (1999), 85-101. doi: 10.1137/S0036144598333613.  Google Scholar

[12]

Optim. Meth. and Soft., 23 (2008), 501-520. doi: 10.1080/10556780802102693.  Google Scholar

[13]

Numer. Math., 100 (2005), 21-47. doi: 10.1007/s00211-004-0569-y.  Google Scholar

[14]

SIAM J. Matrix Anal. Appl., 30 (2008), 56-66. doi: 10.1137/060670985.  Google Scholar

[15]

IEEE Trans. on Image Proc., 14 (2005), 2091-2106. doi: 10.1109/TIP.2005.859376.  Google Scholar

[16]

IEEE Trans. Image Proc., 20 (2011), 1838-1857. doi: 10.1109/TIP.2011.2108306.  Google Scholar

[17]

Inver. Problems, 23 (2007), 947-968. doi: 10.1088/0266-5611/23/3/007.  Google Scholar

[18]

Digit. Sig. Proc., 17 (2007), 32-49. doi: 10.1016/j.dsp.2006.02.002.  Google Scholar

[19]

IEEE J. on Sig. Proc., 1 (2007), 586-597. Google Scholar

[20]

IEEE J. in Sig. Proc., 1 (2007), 586-597. Google Scholar

[21]

Biostatistics, 9 (2008), 432-441. doi: 10.1093/biostatistics/kxm045.  Google Scholar

[22]

Technometrics, 49 (2007), 291-304. doi: 10.1198/004017007000000245.  Google Scholar

[23]

Neu. Comput., 13 (2001), 2517-2532. doi: 10.1162/089976601753196003.  Google Scholar

[24]

Technometrics, 21 (1979), 215-223. doi: 10.1080/00401706.1979.10489751.  Google Scholar

[25]

Geophysics, 69 (2004), 1216-1228. Google Scholar

[26]

IEEE trans. on Nuc. Sci., 44 (1997), 2425-2430. Google Scholar

[27]

SIAM, Philadelphia, 1998. doi: 10.1137/1.9780898719697.  Google Scholar

[28]

Inver. Problems, 25 (2009), 20pp. doi: 10.1088/0266-5611/25/9/095009.  Google Scholar

[29]

Wiley, New York, 1972. Google Scholar

[30]

J. Mach. Learning Research, accepted, 2012. Google Scholar

[31]

Birkhäuser, Boston, 2001.  Google Scholar

[32]

Neu. Comput., 15 (2003), 349-396. doi: 10.1162/089976603762552951.  Google Scholar

[33]

in "Proc. of SPIE," 5914, (2005), 254-262. doi: 10.1117/12.613494.  Google Scholar

[34]

Neu. Comput., 12 (2000), 337-365. doi: 10.1162/089976600300015826.  Google Scholar

[35]

SIAM J. Optim., in press, 2011. Google Scholar

[36]

SIAM J. Optim., 19 (2009), 807-1827. doi: 10.1137/070695915.  Google Scholar

[37]

21 (2009), 1033-1040. Google Scholar

[38]

Academic Press, 2008.  Google Scholar

[39]

Electronics Letters, 27 (1991), 1159-1161. doi: 10.1049/el:19910723.  Google Scholar

[40]

J. VLSI Sig. Proc., 45 (2006), 97-110. doi: 10.1007/s11265-006-9774-5.  Google Scholar

[41]

Technical Report 1673, mitai, (CBCL Memo 180), October 1999. Google Scholar

[42]

Springer-Verlag, New York, 1986.  Google Scholar

[43]

IEEE Trans. on Image Proc., 14 (2005), 423-438. doi: 10.1109/TIP.2005.843753.  Google Scholar

[44]

in "Proc. of Sampta'11," 2011. Google Scholar

[45]

IEEE Trans. on Sig. Proc., 58 (2010), 1553-1564.  Google Scholar

[46]

Cambridge, 2001.  Google Scholar

[47]

Advances in Image and Elect. Phys., 128 (2003), 445-530. Google Scholar

[48]

The Annals of Stat., 6 (1978), 461-464. doi: 10.1214/aos/1176344136.  Google Scholar

[49]

Math. Program., 14 (1978), 149-160. doi: 10.1007/BF01588962.  Google Scholar

[50]

SIGKDD, 2012. Google Scholar

[51]

Neu. Netw., 15 (2002), 349-361. doi: 10.1016/S0893-6080(02)00022-9.  Google Scholar

[52]

J. Royal. Statist. Soc B., 58 (1996), 267-288.  Google Scholar

[53]

Soviet Math. Dokl., 4 (1963), 1035-1038. Google Scholar

[54]

SIAM J. Scient. Comput., 31 (2008), 890-912. doi: 10.1137/080714488.  Google Scholar

[55]

Wiley, 1998.  Google Scholar

[56]

SIAM, Philadelphia, 2002. doi: 10.1137/1.9780898717570.  Google Scholar

[57]

J. R. Statist. Soc. B, 71 (2009), 671-683. doi: 10.1111/j.1467-9868.2008.00693.x.  Google Scholar

[58]

IEEE Trans. on Sig. Proc., 52 (2004), 2153-2164.  Google Scholar

[59]

24 (2011), 900-908. Google Scholar

[60]

SIAM J. Optim., 20, (2009), 627-649. doi: 10.1137/070702187.  Google Scholar

show all references

References:
[1]

IEEE Trans. Auto. Cont., 19 (1974), 716-723. doi: 10.1109/TAC.1974.1100705.  Google Scholar

[2]

IEEE Trans. Auto. Cont., 56 (2011), 2898-2911. doi: 10.1109/TAC.2011.2141430.  Google Scholar

[3]

SIAM J. Scient. Comput., 28 (2006), 339-358. doi: 10.1137/040617261.  Google Scholar

[4]

M2AN, Math. Model. Numer. Anal., 43 (2009), 689-708.  Google Scholar

[5]

Proc. IEEE Intl. Conf. on Acous., Spee., and Sig. Proc., 2000. Google Scholar

[6]

SIAM Review, 51 (2009), 34-81. doi: 10.1137/060657704.  Google Scholar

[7]

E. J. Candès and D. L. Donoho, "Curvelets: A Surprisingly Effective Nonadaptive Representation for Objects with Edges,", 1999., ().   Google Scholar

[8]

IEEE In Sig. Proc. Magaz., 25 (2008), 21-30. doi: 10.1109/MSP.2007.914731.  Google Scholar

[9]

SIAM, 2005.  Google Scholar

[10]

SIAM J. Imaging Sci., 3 (2010), 765-790. doi: 10.1137/080740167.  Google Scholar

[11]

SIAM Review, 41 (1999), 85-101. doi: 10.1137/S0036144598333613.  Google Scholar

[12]

Optim. Meth. and Soft., 23 (2008), 501-520. doi: 10.1080/10556780802102693.  Google Scholar

[13]

Numer. Math., 100 (2005), 21-47. doi: 10.1007/s00211-004-0569-y.  Google Scholar

[14]

SIAM J. Matrix Anal. Appl., 30 (2008), 56-66. doi: 10.1137/060670985.  Google Scholar

[15]

IEEE Trans. on Image Proc., 14 (2005), 2091-2106. doi: 10.1109/TIP.2005.859376.  Google Scholar

[16]

IEEE Trans. Image Proc., 20 (2011), 1838-1857. doi: 10.1109/TIP.2011.2108306.  Google Scholar

[17]

Inver. Problems, 23 (2007), 947-968. doi: 10.1088/0266-5611/23/3/007.  Google Scholar

[18]

Digit. Sig. Proc., 17 (2007), 32-49. doi: 10.1016/j.dsp.2006.02.002.  Google Scholar

[19]

IEEE J. on Sig. Proc., 1 (2007), 586-597. Google Scholar

[20]

IEEE J. in Sig. Proc., 1 (2007), 586-597. Google Scholar

[21]

Biostatistics, 9 (2008), 432-441. doi: 10.1093/biostatistics/kxm045.  Google Scholar

[22]

Technometrics, 49 (2007), 291-304. doi: 10.1198/004017007000000245.  Google Scholar

[23]

Neu. Comput., 13 (2001), 2517-2532. doi: 10.1162/089976601753196003.  Google Scholar

[24]

Technometrics, 21 (1979), 215-223. doi: 10.1080/00401706.1979.10489751.  Google Scholar

[25]

Geophysics, 69 (2004), 1216-1228. Google Scholar

[26]

IEEE trans. on Nuc. Sci., 44 (1997), 2425-2430. Google Scholar

[27]

SIAM, Philadelphia, 1998. doi: 10.1137/1.9780898719697.  Google Scholar

[28]

Inver. Problems, 25 (2009), 20pp. doi: 10.1088/0266-5611/25/9/095009.  Google Scholar

[29]

Wiley, New York, 1972. Google Scholar

[30]

J. Mach. Learning Research, accepted, 2012. Google Scholar

[31]

Birkhäuser, Boston, 2001.  Google Scholar

[32]

Neu. Comput., 15 (2003), 349-396. doi: 10.1162/089976603762552951.  Google Scholar

[33]

in "Proc. of SPIE," 5914, (2005), 254-262. doi: 10.1117/12.613494.  Google Scholar

[34]

Neu. Comput., 12 (2000), 337-365. doi: 10.1162/089976600300015826.  Google Scholar

[35]

SIAM J. Optim., in press, 2011. Google Scholar

[36]

SIAM J. Optim., 19 (2009), 807-1827. doi: 10.1137/070695915.  Google Scholar

[37]

21 (2009), 1033-1040. Google Scholar

[38]

Academic Press, 2008.  Google Scholar

[39]

Electronics Letters, 27 (1991), 1159-1161. doi: 10.1049/el:19910723.  Google Scholar

[40]

J. VLSI Sig. Proc., 45 (2006), 97-110. doi: 10.1007/s11265-006-9774-5.  Google Scholar

[41]

Technical Report 1673, mitai, (CBCL Memo 180), October 1999. Google Scholar

[42]

Springer-Verlag, New York, 1986.  Google Scholar

[43]

IEEE Trans. on Image Proc., 14 (2005), 423-438. doi: 10.1109/TIP.2005.843753.  Google Scholar

[44]

in "Proc. of Sampta'11," 2011. Google Scholar

[45]

IEEE Trans. on Sig. Proc., 58 (2010), 1553-1564.  Google Scholar

[46]

Cambridge, 2001.  Google Scholar

[47]

Advances in Image and Elect. Phys., 128 (2003), 445-530. Google Scholar

[48]

The Annals of Stat., 6 (1978), 461-464. doi: 10.1214/aos/1176344136.  Google Scholar

[49]

Math. Program., 14 (1978), 149-160. doi: 10.1007/BF01588962.  Google Scholar

[50]

SIGKDD, 2012. Google Scholar

[51]

Neu. Netw., 15 (2002), 349-361. doi: 10.1016/S0893-6080(02)00022-9.  Google Scholar

[52]

J. Royal. Statist. Soc B., 58 (1996), 267-288.  Google Scholar

[53]

Soviet Math. Dokl., 4 (1963), 1035-1038. Google Scholar

[54]

SIAM J. Scient. Comput., 31 (2008), 890-912. doi: 10.1137/080714488.  Google Scholar

[55]

Wiley, 1998.  Google Scholar

[56]

SIAM, Philadelphia, 2002. doi: 10.1137/1.9780898717570.  Google Scholar

[57]

J. R. Statist. Soc. B, 71 (2009), 671-683. doi: 10.1111/j.1467-9868.2008.00693.x.  Google Scholar

[58]

IEEE Trans. on Sig. Proc., 52 (2004), 2153-2164.  Google Scholar

[59]

24 (2011), 900-908. Google Scholar

[60]

SIAM J. Optim., 20, (2009), 627-649. doi: 10.1137/070702187.  Google Scholar

[1]

Chih-Chiang Fang. Bayesian decision making in determining optimal leased term and preventive maintenance scheme for leased facilities. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020127
[2]

Ahmad Mousavi, Zheming Gao, Lanshan Han, Alvin Lim. Quadratic surface support vector machine with L1 norm regularization. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021046
[3]

Tengteng Yu, Xin-Wei Liu, Yu-Hong Dai, Jie Sun. Variable metric proximal stochastic variance reduced gradient methods for nonconvex nonsmooth optimization. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021084
[4]

Zhaoxia Wang, Hebai Chen. A nonsmooth van der Pol-Duffing oscillator (I): The sum of indices of equilibria is $ -1 $. Discrete & Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021096
[5]

Zhaoxia Wang, Hebai Chen. A nonsmooth van der Pol-Duffing oscillator (II): The sum of indices of equilibria is $ 1 $. Discrete & Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021101
[6]

Mohsen Abdolhosseinzadeh, Mir Mohammad Alipour. Design of experiment for tuning parameters of an ant colony optimization method for the constrained shortest Hamiltonian path problem in the grid networks. Numerical Algebra, Control & Optimization, 2021, 11 (2) : 321-332. doi: 10.3934/naco.2020028
[7]

Reza Lotfi, Yahia Zare Mehrjerdi, Mir Saman Pishvaee, Ahmad Sadeghieh, Gerhard-Wilhelm Weber. A robust optimization model for sustainable and resilient closed-loop supply chain network design considering conditional value at risk. Numerical Algebra, Control & Optimization, 2021, 11 (2) : 221-253. doi: 10.3934/naco.2020023
[8]

Luke Finlay, Vladimir Gaitsgory, Ivan Lebedev. Linear programming solutions of periodic optimization problems: approximation of the optimal control. Journal of Industrial & Management Optimization, 2007, 3 (2) : 399-413. doi: 10.3934/jimo.2007.3.399
[9]

Woocheol Choi, Youngwoo Koh. On the splitting method for the nonlinear Schrödinger equation with initial data in $ H^1 $. Discrete & Continuous Dynamical Systems, 2021, 41 (8) : 3837-3867. doi: 10.3934/dcds.2021019
[10]

Maolin Cheng, Yun Liu, Jianuo Li, Bin Liu. Nonlinear Grey Bernoulli model NGBM (1, 1)'s parameter optimisation method and model application. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021054
[11]

Qing Liu, Bingo Wing-Kuen Ling, Qingyun Dai, Qing Miao, Caixia Liu. Optimal maximally decimated M-channel mirrored paraunitary linear phase FIR filter bank design via norm relaxed sequential quadratic programming. Journal of Industrial & Management Optimization, 2021, 17 (4) : 1993-2011. doi: 10.3934/jimo.2020055
[12]

Xianbang Chen, Yang Liu, Bin Li. Adjustable robust optimization in enabling optimal day-ahead economic dispatch of CCHP-MG considering uncertainties of wind-solar power and electric vehicle. Journal of Industrial & Management Optimization, 2021, 17 (4) : 1639-1661. doi: 10.3934/jimo.2020038
[13]

Xu Zhang, Zhanglin Peng, Qiang Zhang, Xiaoan Tang, Panos M. Pardalos. Identifying and determining crowdsourcing service strategies: An empirical study on a crowdsourcing platform in China. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021045
[14]

Sabyasachi Dey, Tapabrata Roy, Santanu Sarkar. Revisiting design principles of Salsa and ChaCha. Advances in Mathematics of Communications, 2019, 13 (4) : 689-704. doi: 10.3934/amc.2019041
[15]

Andreas Neubauer. On Tikhonov-type regularization with approximated penalty terms. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2021027
[16]

Tao Wu, Yu Lei, Jiao Shi, Maoguo Gong. An evolutionary multiobjective method for low-rank and sparse matrix decomposition. Big Data & Information Analytics, 2017, 2 (1) : 23-37. doi: 10.3934/bdia.2017006
[17]

Ziteng Wang, Shu-Cherng Fang, Wenxun Xing. On constraint qualifications: Motivation, design and inter-relations. Journal of Industrial & Management Optimization, 2013, 9 (4) : 983-1001. doi: 10.3934/jimo.2013.9.983
[18]

Yi Gao, Rui Li, Yingjing Shi, Li Xiao. Design of path planning and tracking control of quadrotor. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021063
[19]

Kha Van Huynh, Barbara Kaltenbacher. Some application examples of minimization based formulations of inverse problems and their regularization. Inverse Problems & Imaging, 2021, 15 (3) : 415-443. doi: 10.3934/ipi.2020074
[20]

Charles Fulton, David Pearson, Steven Pruess. Characterization of the spectral density function for a one-sided tridiagonal Jacobi matrix operator. Conference Publications, 2013, 2013 (special) : 247-257. doi: 10.3934/proc.2013.2013.247

2019 Impact Factor: 1.373

Tools

Metrics

  • PDF downloads (65)
  • HTML views (0)
  • Cited by (3)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences