DOI: https://doi.org/10.15588/1607-3274-2019-1-15

PROBLEM STATEMENTS OF DATA PROCESSING BASED ON CRITERION OF MINIMUM EXTENT

S. M. Vovk

Abstract


Context. In order to process the data containing anomalous values as well as to obtain the sparse solutions or solutions with small extent, the requirement to minimize the extent of the function used to find solution can be used. In this paper the object of the study is the process of setting the data processing problems on the basis of this requirement, which is further referred to as the criterion of minimum extent.
Objective. The goal of this work is the development of an approach to the formulation of the data processing problems based on criterion of minimum extent. 
Method. On the basis of minimum extent criterion, a new approach is proposed. This approach allows to formulate the data approximation problem as well as the inverse problem with a direct linear operator and with a solution of small extent or with a sparse solution in conditions that the initial data contain noise and anomalous values. The statement of the approximation problem is obtained
by setting a parametric data model and applying the criterion of minimum extent to the solution residual. The statement of the inverse problem is obtained by applying the criterion of minimum extent to the solution of the problem and to the solution residual. The special cases of this statement are presented and it is noted that this statement generalizes the statement of the Tikhonov regularization
problem. The proposed problem statements are formulated as minimization problems for the corresponding functionals constructed on the basis of the “superset” of cost functions. In the general case, the indicated functionals are neither convex nor unimodal, and their minimization can be a laborious task.
Results. The proposed problem statements generalize those that are performed on the basis of the least squares criterion and/or least modules criterion. Numerical simulation of the problem of approximation by a linear function of noisy data in the presence of impulsive noise, as well as in the presence of an interfering fragment of exponential function, confirmed the feasibility of the proposed statement and its effectiveness. Numerical simulation of the inverse problem, corresponded to the overdetermined system of linear algebraic equations with gross errors in its right-hand side and sparse solution, also confirmed the feasibility of using the criterion
of minimum extent for its formulation.
Conclusions. The problem statement of data processing which is based on the criterion of minimum extent is expedient under conditions when the part of the data is roughly distorted and/or when the desired solution has a small extent. The statements based on the criterion of minimum extent allow us to expand the range of the problems to be solved.


Keywords


processing; criterion; extent; approximation; inverse problem.

References


Millar R. B. Maximum Likelihood Estimation and Inference:

With Examples in R, SAS and ADMB. New York,

Wiley, 2011, 376 p.

Huber P., Ronchetti E. M. Robust statistics. 2nd ed. Hoboken,

Wiley, 2009, 370 p.

Tihonov A. N., Goncharskij A. V., Stepanov V. V., Jagola

A. G. Reguljarizirujushhie algoritmy i apriornaja informacija.

Moscow, Nauka, 1983, 200 p.

Wolberg J. Data Analysis Using the Method of Least

Squares: Extracting the Most Information from Experiments.

Berlin, SpringerVerlag, 2005, 250 p.

Chandola V., Banerjee A., Kumar V. Anomaly detection: A

survey, ACM Computing Surveys, 2009, Vol. 41, No. 3,

pp. 15–58.

Elgmati E. A., Gredni N. B. Quartile Method Estimation of

Two-Parameter Exponential Distribution Data with Outliers,

International Journal of Statistics and Probability, 2016,

Vol. 5, No. 5, pp. 12–15.

Shevlyakov G. L., Vilchevski N. O. Robustness in data

analysis: criteria and methods. Utrecht, VSP, 2002, 310 p.

Hampel F. R. Ronchetti E. M., Rousseeuw P. J., Stahel

W. A. Robust statistics: the approach based on influence

functions. Hoboken, NJ, Wiley, 2011, 502 p.

DOI=10.1002/9781118186435.

Demidenko E. Z. Optimizacija i regressija. Moscow, Nauka,

, 296 с.

Aysal T. C., Barner K. E. Meridian filtering for robust signal

processing, IEEE Trans. on Signal Processing, 2007, V. 55,

No. 8, pp. 3949–3962.

Borulko V. F., Vovk S. M. Minimum-duration filtering,

Radio Electronics, Computer Science, Control, 2016, No. 1,

pp. 7–14. DOI: 10.15588/1607-3274-2016-1-1.

Vovk S. M. General approach to building the methods of

filtering based on the minimum duration principle,

Radioelectronics and Communications Systems, 2016,

V. 59, No. 7, pp. 281–292. DOI:

3103/S0735272716070013.

Selesnick I. W., Bayram İ. Enhanced Sparsity by Non-

Separable Regularization, IEEE Transactions on Signal

Processing, 2016, Vol. 64, No. 9, pp. 2298–2313. DOI:

1109/TSP.2016.2518989.

Little M. A., Jones N. S. Generalized methods and solvers

for noise removal from piecewise constant signals. I. Background

theory, Proceedings of the Royal Society A, 2011,

Vol. 467, pp. 3088–3114. DOI:10.1098/rspa.2010.0671.

Little M. A., Jones N. S. Generalized methods and solvers

for noise removal from piecewise constant signals. II. New

methods, Proceedings of the Royal Society A, 2011,

Vol. 467, pp. 3115–3140. DOI: 10.1098/rspa.2010.0674.

Liu Q., Yang C., Gu Y., So H. C. Robust Sparse Recovery

via Weakly Convex Optimization in Impulsive Noise, Signal

Processing, 2018, Vol. 152, pp. 84–89. DOI:

=https://doi.org/10.1016/j.sigpro.2018.05.020.

Titchmarsh E. C. The theory of functions. New York, Oxford

University Press, 1939, 454 p.

Tibshirani R. Regression shrinkage and selection via the

lasso: a retrospective, Journal of the Royal Statistical Society

Series B, 2011, Vol. 73, No. 3, pp. 273–282. DOI=

https://doi.org/10.1111/j.1467-9868.2011.00771.x

Vovk S. M. Metod chislennogo differencirovanija zashumlennyh

dannyh s vybrosami, Radio Electronics, Computer

Science, Control, 2017, No. 3, pp. 44–52. DOI:

15588/1607-3274-2017-3-5].

Vovk S. M., Borul’ko V. F. Dvojstvennyj metod minimuma

prostranstvennoj protjazhennosti dlja robastnogo ocenivanija

parametrov dipol’nyh istochnikov izluchenija, Radio Electronics,

Computer Science, Control, 2014, No. 2, pp. 8–17.

DOI: 10.15588/1607-3274-2014-2-1.


GOST Style Citations


1. Millar R. B. Maximum Likelihood Estimation and Inference:
With Examples in R, SAS and ADMB / R. B. Millar. –
New York: Wiley, 2011. – 376 p.
2. Huber P. Robust statistics. 2nd ed. / P. Huber,
E. M. Ronchetti. – Hoboken : Wiley, 2009. – 370 p.
3. Тихонов А. Н. Регуляризирующие алгоритмы и априор-
ная информация / А. Н. Тихонов, А. В. Гончарский,
В. В. Степанов, А. Г. Ягола. – М. : Наука, 1983. – 200 с.
4. Wolberg J. Data Analysis Using the Method of Least
Squares: Extracting the Most Information from Experiments
/ J. Wolberg. – Berlin : SpringerVerlag, 2005. – 250 p.
5. Chandola V. Anomaly detection: A survey / V. Chandola,
A. Banerjee, V. Kumar // ACM Computing Surveys. –
2009. – Vol. 41, № 3. – P. 15–58.
6. Elgmati E. A. Quartile Method Estimation of Two-
Parameter Exponential Distribution Data with Outliers /
E. A. Elgmati, N. B. Gredni // International Journal of Statistics
and Probability. – 2016. – Vol. 5, № 5. – P. 12–15.
7. Shevlyakov G. L. Robustness in data analysis: criteria and
methods. / G. L. Shevlyakov, N. O. Vilchevski. – Utrecht :
VSP, 2002. – 310 p.
8. Hampel F. R. Robust statistics: the approach based on influence
functions / F. R. Hampel, E. M. Ronchetti,
P. J. Rousseeuw, W. A. Stahel. – Hoboken, NJ : Wiley,
2011. – 502 p. DOI=10.1002/9781118186435.
9. Демиденко Е. З. Оптимизация и регрессия / Е. З. Деми-
денко. – М. : Наука, 1989. – 296 с.
10. Aysal T. C. Meridian filtering for robust signal processing /
T. C. Aysal, K. E. Barner // IEEE Trans. on Signal Processing.
– 2007. – V. 55, № 8. – P. 3949–3962.
11. Borulko V. F. Minimum-duration filtering / V. F. Borulko,
S. M. Vovk // Радіоелектроніка, інформатика,
управління. – 2016. – № 1. – С. 7–14. DOI:
10.15588/1607-3274-2016-1-1.
12. Vovk S. M. General approach to building the methods of
filtering based on the minimum duration principle /
S. M. Vovk // Radioelectronics and Communications Systems.
– 2016. – V. 59, № 7. – P. 281–292. DOI:
10.3103/S0735272716070013.
13. Selesnick I. W. Enhanced Sparsity by Non-Separable Regularization
/ I. W. Selesnick, İ. Bayram // IEEE Transactions
on Signal Processing. – 2016. – Vol. 64, № 9. –
P. 2298 2313. DOI: 10.1109/TSP.2016.2518989.
14. Little M. A. Generalized methods and solvers for noise removal
from piecewise constant signals. I. Background theory
/ M. A. Little, N. S. Jones // Proceedings of the Royal
Society A. – 2011. – Vol. 467. – P. 3088–3114. DOI:
10.1098/rspa.2010.0671.
15. Little M. A. Generalized methods and solvers for noise removal
from piecewise constant signals. II. New methods /
M. A. Little, N. S. Jones // Proceedings of the Royal Society
A. – 2011. – Vol. 467. – P. 3115–3140. DOI:
10.1098/rspa.2010.0674.
16. Liu Q. Robust Sparse Recovery via Weakly Convex Optimization
in Impulsive Noise / Q. Liu, C. Yang, Y. Gu,
H. C. So // Signal Processing. – 2018. – Vol. 152. – P. 84–
89. DOI: =https://doi.org/10.1016/j.sigpro.2018.05.020.
17. Titchmarsh E. C. The theory of functions / E. C. Titchmarsh.
– New York : Oxford University Press, 1939. –
454 p.
18. Tibshirani R. Regression shrinkage and selection via the
lasso: a retrospective / R. Tibshirani // Journal of the Royal
Statistical Society Series B. – 2011. – Vol. 73, № 3. –
P. 273–282. DOI= https://doi.org/10.1111/j.1467-
9868.2011.00771.x
19. Вовк С. М. Метод численного дифференцирования за-
шумленных данных с выбросами / С. М. Вовк //
Радіоелектроніка, інформатика, управління. – 2017. –
№ 3 – С. 44–52. DOI: 10.15588/1607-3274-2017-3-5].
20. Вовк С. М. Двойственный метод минимума пространст-
венной протяженности для робастного оценивания па-
раметров дипольных источников излучения /
С. М. Вовк, В. Ф. Борулько // Радіоелектроніка,
інформатика, управління. – 2014. – № 2. – С. 8–17. DOI:
10.15588/1607-3274-2014-2-1.







Copyright (c) 2019 S. M. Vovk

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

Address of the journal editorial office:
Editorial office of the journal «Radio Electronics, Computer Science, Control»,
National University "Zaporizhzhia Polytechnic", 
Zhukovskogo street, 64, Zaporizhzhia, 69063, Ukraine. 
Telephone: +38-061-769-82-96 – the Editing and Publishing Department.
E-mail: rvv@zntu.edu.ua

The reference to the journal is obligatory in the cases of complete or partial use of its materials.