×

Relaxed maximum a posteriori fault identification. (English) Zbl 1161.94376

Summary: We consider the problem of estimating a pattern of faults, represented as a binary vector, from a set of measurements. The measurements can be noise corrupted real values, or quantized versions of noise corrupted signals, including even 1-bit (sign) measurements. Maximum a posteriori probability (MAP) estimation of the fault pattern leads to a difficult combinatorial optimization problem, so we propose a variation in which an approximate maximum a posteriori probability estimate is found instead, by solving a convex relaxation of the original problem, followed by rounding and simple local optimization. Our method is extremely efficient, and scales to very large problems, involving thousands (or more) of possible faults and measurements. Using synthetic examples, we show that the method performs extremely well, both in identifying the true fault pattern, and in identifying an ambiguity group, i.e., a set of alternate fault patterns that explain the observed measurements almost as well as our estimate.

MSC:

94A13 Detection theory in information and communication theory
94A12 Signal theory (characterization, reconstruction, filtering, etc.)
93E10 Estimation and detection in stochastic control theory

Software:

fast_mpc; SDPT3; CVX
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] D. Viassolo, S. Adibhatla, B. Brunell, J. Down, N. Gibson, A. Kumar, H. Mathews, L. Holcomb, Advanced estimation for aircraft engines, in: Proceedings of the American Control Conference, 2007, pp. 2807 – 2821.
[2] S. Ganguli, S. Deo, D. Gorinevsky, Parametric fault modeling and diagnostics of a turbofan engine, in: Proceedings of the IEEE International Conference on Control Applications, 2004, pp. 223 – 228.
[3] Hoskins, J.; Kaliyur, K.; Himmelblau, D.: Fault diagnosis in complex chemical plants using artificial neural networks, A.i.ch.e. journal 37, No. 1, 137-141 (1991)
[4] Gertler, J.; Costin, M.; Fang, X.; Hira, R.; Kowalczuk, Z.; Luo, Q.: Model-based on-board fault detection and diagnosis for automotive engines, Control engineering practice 1, No. 1, 3-17 (1993)
[5] Hood, C.; Ji, C.: Proactive network-fault detection, IEEE transactions on reliability 46, No. 3, 333-341 (1997)
[6] F. Feather, D. Siewiorek, R. Maxion, Fault detection in an ethernet network using anomaly signature matching, Applications, Technologies, Architectures, and Protocols for Computer Communication (1993) 279 – 288.
[7] Stelling, P.; Dematteis, C.; Foster, I.; Kesselman, C.; Lee, C.; Von Laszewski, G.: A fault detection service for wide area distributed computations, Cluster computing 2, No. 2, 117-128 (1999)
[8] Bandler, J.; Salama, A.: Fault diagnosis of analog circuits, Proceedings of the IEEE 73, No. 8, 1279-1325 (1985)
[9] Frank, P.: Fault diagnosis in dynamic systems using analytical and knowledge-based redundancy — A survey and some new results, Automatica 26, No. 3, 459-474 (1990) · Zbl 0713.93052 · doi:10.1016/0005-1098(90)90018-D
[10] Saberi, A.; Stoorvogel, A.; Sannuti, P.: Fundamental problems in fault detection and identification, International journal of robust nonlinear control 10, 1209-1236 (2000) · Zbl 0967.93037 · doi:10.1002/1099-1239(20001215)10:14<1209::AID-RNC524>3.0.CO;2-C
[11] U. Lerner, R. Parr, D. Koller, G. Biswas, Bayesian fault detection and diagnosis in dynamic systems, in: Proceedings of the American Association of Artificial Intelligence, 2000, pp. 531 – 537.
[12] Morari, M.; Bemporad, A.; Mignone, D.: A framework for control, state estimation, fault detection, and verification of hybrid systems, Scientific computing in chemical engineering II 2, 46-61 (1999)
[13] Isermann, R.: Process fault detection based on modeling and estimation methods, Automatica 20, No. 4, 387-404 (1984) · Zbl 0539.90037 · doi:10.1016/0005-1098(84)90098-0
[14] Gertler, J.: Fault detection and diagnosis in engineering systems, (1998)
[15] Goodwin, G.; Seron, M.; Doná, J. D.: Constrained control and estimation: an optimisation approach, (2004)
[16] Reiter, R.: A theory of diagnosis from first principles, Artificial intelligence 32, No. 1, 57-95 (1987) · Zbl 0643.68122 · doi:10.1016/0004-3702(87)90062-2
[17] De Kleer, J.; Williams, B.: Diagnosing multiple faults, Artificial intelligence 32, No. 1, 97-130 (1987) · Zbl 0642.94045 · doi:10.1016/0004-3702(87)90063-4
[18] F. Tu, K. Pattipati, S. Deb, V. Malepati, Multiple fault diagnosis in graph-based systems, in: Proceedings of SPIE, Component and Systems Diagnostics, Prognostics, and Health Management II, 2002, pp. 168 – 179.
[19] Tu, F.; Pattipati, K.; Deb, S.; Malepati, V.: Computationally efficient algorithms for multiple fault diagnosis in large graph-based systems, IEEE transactions on systems, man and cybernetics, part A 33, No. 1, 73-85 (2003)
[20] Donoho, D.: Compressed sensing, IEEE transactions on information theory 52, No. 4, 1289-1306 (2006) · Zbl 1288.94016
[21] Tibshirani, R.: Regression shrinkage and selection via the lasso, journal of the royal statistical society, Series B (Methodological) 58, No. 1, 267-288 (1996) · Zbl 0850.62538
[22] Tropp, J.: Just relax: convex programming methods for identifying sparse signals in noise, IEEE transactions on information theory 52, No. 3, 1030-1051 (2006) · Zbl 1288.94025
[23] J. Feldman, D. Karger, M. Wainwright, LP decoding, in: Proceedings of the 41st Allerton Conference on Communications, Control, and Computing, Monticello, Illinois, USA, 2003, pp. 1 – 3.
[24] Lobo, M.; Fazel, M.; Boyd, S.: Portfolio optimization with linear and fixed transaction costs, Annals of operations research 152, No. 1, 341-365 (2007) · Zbl 1132.91474 · doi:10.1007/s10479-006-0145-1
[25] A. Hassibi, J. How, S. Boyd, Low-authority controller design via convex optimization, in: Proceedings of the IEEE Conference on Decision and Control, vol. 1, 1998.
[26] L. Vandenberghe, S. Boyd, A. E. Gamal, Optimal wire and transistor sizing for circuits with non-tree topology, in: Proceedings of the 1997 IEEE/ACM International Conference on Computer Aided Design, 1997, pp. 252 – 259.
[27] S. Joshi, S. Boyd, Sensor selection via convex optimization, in: IEEE Transactions on Signal Processing, available from \langle&nbsp;www.stanford.edu/&sim;boyd/sensor_selection.html\rangle&nbsp; 2008, to appear. · Zbl 1391.90679
[28] A. Zymnis, S. Boyd, D. Gorinevsky, Mixed state estimation for a linear gaussian markov model, in: Proceedings of the IEEE Conference on Decision and Control, 2008, to appear. · Zbl 1177.94081
[29] Tan, P.; Rasmussen, L.: The application of semidefinite programming for detection in CDMA, IEEE journal on selected areas in communications 19, No. 8, 1442-1449 (2001)
[30] Abdi, M.; Nahas, H.; Jard, A.; Moulines, E.: Semidefinite positive relaxation of the maximum-likelihood criterion applied to multiuser detection in a CDMA context, IEEE signal processing letters 9, No. 6, 165-167 (2002)
[31] M. Kisialiou, Z. Q. Luo, Performance analysis of quasi-maximum-likelihood detector based on semi-definite programming, in: Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing, vol. 3, Philadelphia, PA, 2005.
[32] Tan, P. H.; Rasmussen, L. K.: Multiuser detection in CDMA — a comparison of relaxations, exact, and heuristic search methods, IEEE transactions on wireless communications 3, No. 5, 1802-1809 (2004)
[33] J. Jaldén, C. Martin, B. Ottersten, Semidefinite programming for detection in linear systems — optimality conditions and space-time decoding, in: IEEE International Conference on Acoustics, Speech, and Signal Processing, 2003.
[34] J. Jaldén, B. Ottersten, W.-K. Ma, Reducing the average complexity of ML detection using semidefinite relaxation, in: Proceedings IEEE International Conference on Acoustics, Speech, and Signal Processing, 2005.
[35] Jaldén, J.; Ottersten, B.: The diversity order of the semidefinite relaxation detector, IEEE transactions on information theory 54, 1406-1422 (2008) · Zbl 1328.94024
[36] A. Montanari, D. Tse, Analysis of belief propagation for nonlinear problems: The example of CDMA, in: Proceedings of the IEEE Information Theory Workshop, Punta del Este, Uruguay, 2006.
[37] A. Montanari, B. Prabhakar, D. Tse, Belief propagation based multi – user detection, in: Proceedings 43th Allerton Conference on Communications, Control and Computing, Monticello, IL, USA, 2005.
[38] D. Bickson, O. Shental, P. H. Siegel, J. K. Wolf, D. Dolev, Gaussian belief propagation based multiuser detection, in: IEEE International Symposium on Information Theory, Toronto, Canada, July 2008.
[39] B. L. Ng, J. Evans, S. Hanly, Distributed downlink beamforming in cellular networks, in: IEEE International Symposium on Information Theory (ISIT), Nice, France, June 2007.
[40] Kschischang, F.; Frey, B.; Loeliger, H. -A.: Factor graphs and the sum-product algorithm, IEEE transactions on information theory 47, No. 2, 498-519 (2001) · Zbl 0998.68234 · doi:10.1109/18.910572
[41] Yedidia, J.; Freeman, W.; Weiss, Y.: Constructing free-energy approximations and generalized belief propagation algorithms, IEEE transactions on information theory 51, No. 7, 2282-2312 (2005) · Zbl 1283.94023
[42] Boyd, S.; Vandenberghe, L.: Convex optimization, (2004) · Zbl 1058.90049
[43] Lawler, E.; Wood, D.: Branch-and-bound methods: a survey, Operations research 14, 699-719 (1966) · Zbl 0143.42501 · doi:10.1287/opre.14.4.699
[44] Moore, R.: Global optimization to prescribed accuracy, Computers and mathematics with applications 21, No. 6 – 7, 25-39 (1991) · Zbl 0725.65062 · doi:10.1016/0898-1221(91)90158-Z
[45] Nocedal, J.; Wright, S.: Numerical optimization, (1999) · Zbl 0930.65067
[46] M. Grant, S. Boyd, Y. Ye, CVX Version 1.1. Matlab Software for Disciplined Convex Programming, available from \langle&nbsp;www.stanford.edu/&sim;boyd/cvx/\rangle&nbsp;, 2007.
[47] K. Toh, R. Tütüncü, M. Todd, SDPT3 Version 4.0. A Matlab software for semidefinite-quadratic-linear programming, available from \langle&nbsp;www.math.nus.edu.sg/&sim;mattohkc/sdpt3.html\rangle&nbsp;, 2006.
[48] Nesterov, Y.; Wolkowicz, H.; Ye, Y.: Semidefinite programming relaxations of nonconvex quadratic optimization, , 363-419 (2000) · Zbl 0957.90528
[49] Boyd, S.; Wegbreit, B.: Fast computation of optimal contact forces, IEEE transactions on robotics 23, No. 6, 1117-1132 (2007)
[50] Wang, Y.; Boyd, S.: Fast model predictive control using online optimization, , 6974-6997 (2008)
[51] Nesterov, Y.; Nemirovskii, A.: Interior-point polynomial algorithms in convex programming, (1994) · Zbl 0824.90112
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.