×
Wen, You-Wei; Wang, Man; Cao, Zhiying; Cheng, Xiaoqing; Ching, Wai-Ki; Vassiliadis, Vassilios S.

Sparse solution of nonnegative least squares problems with applications in the construction of probabilistic Boolean networks. (English) Zbl 1349.65140

Numer. Linear Algebra Appl. 22, No. 5, 883-899 (2015).
The authors propose a projection-based gradient descent method for numerical computation of sparse solutions of constrained least squares problems. In each iteration, a projection operator can be also viewed as a soft-thresholding operator where the value of the thresholding is adaptively changing during the iterations. To illustrate the performance of the proposed algorithm, the authors apply the proposed algorithm to solve the inverse problem of constructing a probabilistic Boolean network.
Reviewer: Constantin Popa (Constanţa)

Cited in 6 Documents

MSC:

65F20 Numerical solutions to overdetermined systems, pseudoinverses
65F10 Iterative numerical methods for linear systems
65F22 Ill-posedness and regularization problems in numerical linear algebra
65C50 Other computational problems in probability (MSC2010)

Keywords:

gradient descent method; least squares; projection; probabilistic Boolean networks; sparse solutions; algorithm; inverse problem

Software:

Matlab
Cite Review PDF
Full Text: DOI

References:

[1] BjorckA. Numerical Methods for Least Squares Problems. Number 51. SIAM: Philadelphia, USA, 1996. · Zbl 0847.65023
[2] GolubGH, Van LoanCF. Matrix Computations. Johns Hopkins University Press: Baltimore, USA, 1996. · Zbl 0865.65009
[3] BellaviaS, MacconiM, MoriniB. An interior point Newton‐like method for non‐negative least‐squares problems with degenerate solution. Numerical Linear Algebra with Applications2006; 13(10):825-846. · Zbl 1174.65414
[4] EsserE, LouY, XinJ. A method for finding structured sparse solutions to nonnegative least squares problems with applications. SIAM Journal on Imaging Sciences2013; 6(4):2010-2046. · Zbl 1282.90239
[5] KimD, SraS, DhillonI. A non‐monotonic method for large‐scale non‐negative least squares. Optimization Methods and Software2013; 28(5):1012-1039. · Zbl 1310.93089
[6] SlawskiM, HeinM. Non‐negative least squares for high‐dimensional linear models: consistency and sparse recovery without regularization. Electronic Journal of Statistics2013; 7:3004-3056. · Zbl 1280.62086
[7] BrodieJ, DaubechiesI, De MolC, GiannoneD, LorisI. Sparse and stable Markowitz portfolios. Proceedings of the National Academy of Sciences2009; 106(30):12267-12272. · Zbl 1203.91271
[8] ChenC, LiX, TolmanC, WangS, YeY. Sparse portfolio selection via quasi‐norm regularization. arXiv preprint arXiv:1312.6350, 2013.
[9] ChingW, ChenX, TsingN. Generating probabilistic Boolean networks from a prescribed transition probability matrix. IET Systems Biology2009; 3(6):453-464.
[10] ShmulevichI, DoughertyER. Probabilistic Boolean Networks: The Modeling and Control of Gene Regulatory Networks. SIAM: Philadelphia, USA, 2010. · Zbl 1320.92020
[11] FrankM, WolfeP. An algorithm for quadratic programming. Naval Research Logistics Quarterly1956; 3(1-2):95-110.
[12] MerrittM, ZhangY. Interior‐point gradient method for large‐scale totally nonnegative least squares problems. Journal of Optimization Theory and Applications2005; 126(1):191-202. · Zbl 1093.90084
[13] MoriniB, PorcelliM, ChanRH. A reduced newton method for constrained linear least‐squares problems. Journal of Computational and Applied Mathematics2010; 233(9):2200-2212. · Zbl 1186.65049
[14] AfonsoM, Bioucas‐DiasJ, FigueiredoM. Fast image recovery using variable splitting and constrained optimization. IEEE Transactions on Image Processing2010; 19(9):2345-2356. · Zbl 1371.94018
[15] BoydS, VandenbergheL. Convex Optimization. Cambridge University Press: Cambridge, UK, 2009.
[16] CombettesPL, WajsVR. Signal recovery by proximal forward‐backward splitting. Multiscale Modeling and Simulation2005; 4(4):1168-1200. · Zbl 1179.94031
[17] KonnovI. Application of the proximal point method to nonmonotone equilibrium problems. Journal of Optimization Theory and Applications2003; 119(2):317-333. · Zbl 1084.49009
[18] TibshiraniR. Regression shrinkage and selection via the lasso. Journal of the Royal Statistical Society. Series B (Methodological)1996; 58(1):267-288. · Zbl 0850.62538
[19] CandèsE, TaoT. Near‐optimal signal recovery from random projections: universal encoding strategies. IEEE Transactions on Information Theory2006; 52(12):5406-5425. · Zbl 1309.94033
[20] CandèsE, WakinM. An introduction to compressive sampling. IEEE Signal Processing Magazine2008; 25(2):21-30.
[21] DonohoD, EladM, TemlyakovV. Stable recovery of sparse overcomplete representations in the presence of noise. IEEE Transactions on Information Theory2006; 52(1):6-18. · Zbl 1288.94017
[22] ChanR, TaoM, YuanX. Linearized alternating direction method of multipliers for constrained linear least‐squares problem. East Asian Journal on Applied Mathematics2012; 2(4):326-341. · Zbl 1284.68624
[23] MaL, NgM, YuJ, ZengT. Efficient box‐constrained TV‐type��l^1 algorithms for restoring images with impulse noise. Journal of Computational Mathematics2013; 31:249-270. · Zbl 1289.94012
[24] ZhangJ, MoriniB. Solving regularized linear least‐squares problems by alternating direction methods with applications to image restoration. Electronic Transactions on Numerical Analysis2013; 40:356-372. · Zbl 1288.65090
[25] ChenX, NashedZ, QiL. Smoothing methods and semismooth methods for nondifferentiable operator equations. SIAM Journal on Numerical Analysis2000; 38(4):1200-1216. · Zbl 0979.65046
[26] BrucksteinA, EladM, ZibulevskyM. On the uniqueness of nonnegative sparse solutions to underdetermined systems of equations. IEEE Transactions on Information Theory2008; 54(11):4813-4820. · Zbl 1319.15007
[27] deJongH. Modeling and simulation of genetic regulatory systems: a literature review. Journal of Computational Biology2002; 9:69-103.
[28] SmolenP, BaxterD, ByrneJ. Mathematical modeling of gene networks. Neuron2000; 26:567-580.
[29] GuJ, ChingW, SiuT, ZhengH. On modeling credit defaults: a probabilistic Boolean network approach. Risk and Decision Analysis2013; 4:119-129. · Zbl 1294.91182
[30] KauffmanS. Metabolic stability and epigenesis in randomly constructed gene nets. Journal of Theoretical Biology1969; 22:437-467.
[31] KauffmanS. The Origins of Order: Self‐organization and Selection in Evolution. Oxford University Press: New York, 1993.
[32] ShmulevichI, DoughertyE, KimS, ZhangW. From Boolean to probabilistic Boolean networks as models of genetic regulatory networks. Proceedings of the IEEE2002; 90:1778-1792.
[33] ChingW, ZhangS, NgM, AkutsuT. An approximation method for solving the steady‐state probability distribution of probabilistic Boolean networks. Bioinformatics2007; 23:1511-1518.
[34] ChenX, ChingW, ChenXS, CongY, TsingN. Construction of probabilistic Boolean networks from a prescribed transition probability matrix: a maximum entropy rate approach. East Asian Journal of Applied Mathematics2011; 1:132-154. · Zbl 1287.65045
[35] ZhangX, ChanT. Wavelet inpainting by nonlocal total variation. Inverse Problems and Imaging2010; 4(1):191-210. · Zbl 1185.42040
[36] JaggiM. Revisiting Frank-Wolfe: projection-free sparse convex optimization. In Proceedings of the 30th International Conference on Machine Learning, vol. 28, DasguptaS (ed.), McallesterD (ed.) (eds)., JMLR Workshop and Conference Proceedings, Atlanta, US, 2013; 427-435.
[37] ChenX, JiangH, ChingW. On construction of sparse probabilistic Boolean networks. East Asian Journal of Applied Mathematics2012; 2:1-18. · Zbl 1284.60141
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.