Article information

2017 , Volume 22, ¹ 2, p.50-58

Kreinovich V., Neumaier A.

For piecewise smooth signals, l 1 - method is the best among l p - methods: an interval-based justification of an empirical fact

Traditional engineering techniques often use the Least Squares Method (i. e., in mathematical terms, minimization of the 𝑙 2 -norm) to process data. It is known that in many real-life situations, 𝑙 𝑝 -methods with 𝑝 ≠2 lead to better results, and different values of 𝑝 are optimal in different practical cases. In particular, when we need to reconstruct a piecewise smooth signal, the empirically optimal value of 𝑝 is close to 1. In this paper, we provide a new theoretical explanation for this empirical fact based on ideas and results from interval analysis.

[full text]
Keywords: piecewise smooth signal, l 1- method, interval uncertainty

Author(s):
Kreinovich Vladik
Professor
Position: Professor
Office: University of Texas of El Paso
Address: 79968, USA, El Paso, 500, W. University
Phone Office: (915) 747-6951
E-mail: vladik@utep.edu

Neumaier Arnold
Professor
Position: Professor
Office: University of Vienna
Address: Austria, Vienna, A-1090, Vienna, 500, W. University
Phone Office: (431) 4277 50661
E-mail: Arnold.Neumaier@univie.ac.at

References:
[1] Ascher, U.M., Haber, E., Huang, H. On effective methods for implicit piecewise smooth surface recovery. SIAM Journal on Scientific Computing. 2006; 28(1):339–358.
[2] Averill, M.G., Miller, K.C., Keller, G.R., Kreinovich, V., Araiza, R., Starks, S.A. Using expert knowledge in solving the seismic inverse problem. Proceedings of the 24th International Conference of the North American Fuzzy Information Processing Society (NAFIPS’2005). Ann Arbor, Michigan, June 22–25, 2005.
USA: Ann Arbor, Michigan; 2005: 310–314.
[3] Averill, M.G., Miller, K.C., Keller, G.R., Kreinovich, V., Araiza, R., Starks, S.A. Using expert knowledge in solving the seismic inverse problem. East Journal on Approximations. Reasoning (to appear).
[4] Bickel, P.J., Lehmann, E.L. Descriptive statistics for nonparametric models. 1. Introduction. Annals of Statistics. 1975; (3):1045–1069.
[5] Cabrera, S.D., Iyer, K., Xiang, G., Kreinovich, V. On inverse halftoning: computational complexity and interval computations. Proceedings of the 39th Conference on Information Sciences and Systems (CISS’2005), March 16–18, 2005. John Hopkins University; 2005: Paper 164.
[6] Doser, D.I., Crain, K.D., Baker, M.R., Kreinovich, V., Gerstenberger, M.C. Estimating uncertainties for geophysical tomography. Reliable Computing. 1998; 4(3):241– 268.
[7] Feng, H., Casta˜non D.A., Karl W.C. Underground imaging based on edge-preserving regularization. Proceedings of the IEEE International Conference on Information Intelligence and Systems, October 31 – November 3, 1999, Bethesda, Maryland. Los Alamitos, California: IEEE Computer Society; 1999: 460–464.
[8] Huber, P.J. Robust statistics. New York.: Wiley; 1981: 320.
[9] Kaufman, L.C., Neumaier, A. PET regularization by envelope guided conjugate gradients. IEEE Transactions on Medical Imaging. 1996; (15):385–389.
[10] Kaufman, L.C., Neumaier, A. Regularization of ill-posed problems by envelope guided conjugate gradients. Journal of Computational and Graphical Statistics. 1997; (6):451–463.
[11] Nguyen, H.T., Kreinovich, V. Applications of continuous mathematics to computer science. Kluwer, Dordrecht; 1997: 419.
[12] Nikolova, M. Minimizations of cost-functions involving nonsmooth data fidelity terms. Siam Journal On Numerical Analysis. 2002; (40):965–994.
[13] Novitskiy, P.V., Zograph, I.A. Otsenka pogreshnostey rezul'tatov izmereniy [Estimating the measurement errors]. Leningrad: Energoatomizdat; 1991: 304. (In Russ.)
[14] Orlov, A.I. How often are the observations normal? Industrial Laboratory. 1991; 57(7):770–772.
[15] Rabinovich, S.G. Measurement errors and uncertainties: theory and practice. New York: Springer-Verlag; 2005: 308.
[16] Sheskin, D.J. Handbook of parametric and nonparametric statistical procedures. 3rd edition. Boca Raton, Florida: Chapman & Hall/CRC; 2003: 1232.
[17] Tarantola, A. Inverse problem theory: methods for data fitting and model parameter estimation. Amsterdam: Elsevier; 1987: 613.
[18] Wadsworth, H.M. Handbook of statistical methods for engineers and scientists. New York: McGraw-Hill; 1990: 736.
[19] Zhou, J., Shu, H., Xia, T., Luo, L. PET image reconstruction using Mumford-Shah regularization coupled with L 1 data fitting. Proceedings of the 27th Annual IEEE Conference on Engineering in Medicine and Biology, China, September 1–4, 2005. China; 2005: 1905–1908.
[20] Zyskind, G., Martin, F. B. On best linear estimation and a general Gauss-Markov theorem in linear models with arbitrary nonnegative covariance structure. SIAM Journal on Applied Mathematics. 1969; (17):1190–1202.

Bibliography link:
Kreinovich V., Neumaier A. For piecewise smooth signals, l 1 - method is the best among l p - methods: an interval-based justification of an empirical fact // Computational technologies. 2017. V. 22. ¹ 2. P. 50-58
Home| Scope| Editorial Board| Content| Search| Subscription| Rules| Contacts
ISSN 1560-7534
© 2024 FRC ICT