Bursts of Ingrid get

Thirty years ago, the name Ingrid Dobeshi was on the lips of everyone who was in contact with the theory of functions and the theory of approximations. A young woman, a professor of Princeton University, managed to complete the work of several generations of mathematicians and build a system of functions that successfully replace the system of sinuses and cosinuses (Fourier system), to transform functions and their decomposition into ranks. On the miraculous properties of the new system, called Wavelets, venivles (literally - “wolves”, unlike “waves” - sinuses and cosinuses), constantly speech at seminars and university sidelines. Theorists immediately applied the “wolves” to several well-known tasks of functional analysis, physicists with their help built solutions of equations in private derivatives, and the computers improved the Galerkin method, receiving the now famous Vaivette-Galerkin method. All this was, so to speak, by side results. The main purpose of the new system of functions is in the theory of processing and storage of signals. It was there that they committed a real revolution, allowing you to compress the information 100-150 times without a significant loss of quality. The subsequently developed JPEG 2000 format was based on the functions of goodbye.

The term “outbursts” proposed by K. I. Oskolkov took root in Russian -speaking literature. In the mid-1990s, even specialists were very lacked in Russia on this topic: there were no Russian-speaking, English-speaking was not available. The book of the reached “Ten Lectures on Wavelets” (“Ten Lectures on the Splaw”) was in hand in two or three copies, but their owners reluctantly gave them even to copy. Another copy was seen in the “Bukinist” on the Kuznetsk bridge for a hundred dollars - money unreal for those times (this is still expensive for the book). Therefore, already in 1994, Professor Mehmat, Moscow State University S. B. Stechkin, announced the special course “The introduction of bursts into the theory”. He began the first lecture, turning to the audience:

“Open notebooks and write down:

Theorem 1 . Bursts are very important in science and in life.

All recorded the theorem? "

The listeners looked at each other with hidden bewilderment. Stechkin calmly continued:

" Proof. On the World Mathematical Congresses, held once every four years, the most outstanding mathematicians are proposed to make a plenary report. Duration - exactly one hour, there are no exceptions. At the last Congress in Zurich, Dobeshi was given two hours. The theorem is proven. "

What did Ingrid do, and why did this cause such a resonance? First, we need to recall the main provisions of the theory of signal processing (Signal Processing). Signals are continuous - these are functions (for certainty - on the segment [0 , 1]) - and discrete - these are simply sets of n numbers, or vector in the space of R N. You can move from one form to another: replace the function f ( t ) with a discrete signal by removing its values ​​on a uniform grid x k = f ( k/n), k = 0 , ..., n –1; Or, on the contrary, from a discrete signal x = ( x 0 , ..., x n - 1) make a continuous function, setting the value in the breakdown nodes f ( k/n) = x k and connecting them, for example, broken. The dimension of the signal N can be large enough. For storage of photographs of medium quality, if you store it “by points”, N needs N orderly 107. Of course, such huge data arrays are inconvenient for storage and transfer. How to do a smaller number? The main idea is that, as a rule, we need not all signals, but only a particular class, and it can be described much less than N, the number of parameters. Imagine, for example, that we are dealing only with quadratic functions f ( t ) = at 2 + bt + c . Then only three numbers are needed to store the signal - A, B and C. In reality, dealing, say, with audio or video signals, we need a class of smooth or piece-and-core functions. Smooth functions can be well close to a small number of basic "simple" functions. The choice of basic functions for signals of a certain class is one of the main tasks of the theory of signal processing. You can choose the steppe functions 1 , t, t 2 , ... and bring the signal by polynomas as a basis. But technically, this is inconvenient: high degrees become disappearingly small in the entire interval (0 , 1), with the exception of a small surroundings of a unit. It is much better closer to trigonometric polynomas and use trigonometric basic functions Cos 2 π KT and Sin 2 π KT . Thus, for storing smooth signals, the following scheme is taken: a discrete signal is replaced continuous, laid out in a row of Fourier, after which only the first K coefficients of the row are left, the rest are thrown away. The number K depends on the alleged smoothness of the signal and on the accuracy of approaching. So, at n = 107, to approach the class C 1 (with a continuous derivative) with the maximum error ε = 10-3, you will need to store about 106 coefficients. Thus, the volume of information is compressed 10 times without significant loss of quality. Not bad! In addition, a Fourier algorithm was developed to calculate the Fourier coefficients, which spends the order of N LN N operations (for calculating n coefficients). The Fourier method serves as faith and the truth of more than two centuries, however, with the development of computer technology and an increase in the volume of data, a number of its shortcomings have appeared. Main: decomposition in a row Fourier is unstable to noise. Noise is a function with a small carrier and a large meaning. This is a click, crack. The presence of noise when rewriting from magnetic media and signal transmission is inevitable. The increase in the noise changes all the factors of Fourier evenly. After maintaining the final number of coefficients and the reverse converting of Fourier, we get a uniformly spoiled signal. After that, the noise is difficult to localize and eliminate. The reason for this behavior is the fact that the transformation of Fourier does not maintain the compactness of the carrier of functions. For example, the transformation of Fourier Δ -function of Dirac is an identical unit. This is not surprising, since the Fourier system consists of trigonometric functions that themselves are not localized in the straight line: they are not only not final (do not have compact media), but also do not decrease at infinity. Therefore, there can be only one way out: to present a new system of functions that would consist of rapidly decreasing functions (ideally from the finite) and, it would be nice, it would be orthogonal, like trigonometric. One such system was already available! This is the Basis of Haara, built back in 1909. Each HAAR system systems accepts only 1 and 1 values ​​in small intervals, and beyond their borders is zero. Moreover, the special structure of the Haara system, when all the functions are obtained from one “maternal” function using whole shifts and binary compression, allows you to quickly calculate all the decomposition coefficients using the so -called stunt algorithm. He works faster than the rapid transformation of Fourier - spends order n operations! But the functions of Haara are explosive, and the decomposition ranks along this system converge slowly. Is it possible to build a system of smooth functions with the properties of the Haar system? Localization and binary structure?

Is there a “smooth hara”? This question in one form or another stood for decades. He decided gradually. In the 1930-1940s, the Shannona-Kotelnikov system was built, based on shifts with compression of the SINC T = (Sin T ) / T function. The engineers found it rather than mathematicians, since these functions naturally arise in electronics.

As you can see, they slowly decrease at infinity, like 1/ t with t → و. Thus, the bursts of Shannon - Kotelnikov, having good smoothness, have poor localization (albeit better than Fourier). Then there were the bases of Mall, Battla - Lemary and others. Iva Meyer bursts were the breakthrough in 1986, which, along with smoothness, quickly decreased. In fact, Meyer “corrected” Shannon -Kotelnikov’s mother function, but this amendment demanded a new and very complex design. Unlike the latter, Meyer's bursts were not taken “from life”, but were completely man -made. In 2017, Yves Meyer received a prize of Abel for them. However, Meyer bursts are not a smooth hawar, it is rather “quickly decreasing Shannon - Kotelnikov,” since the functions of Haar are not finite. Ingrid Dobeshi, a 42-year-old employee of the AT & T Bell Laboratory scientific center in New Jersey (USA), who had just arrived from Belgium, took up the task of building smooth Haara. Her profession was mathematical physics and quantum mechanics, in which she very successfully established herself. But in a new place, she took up the problems of signal processing and, of course, immediately reached the theory of bursts. The construction of finite bursts required actually a new theory. Initially, the reached showed that it is necessary to solve the scaling equation gment ∈ ( t) = σ nk = 0 c k ng (2 t - k ) - a variety equation on the function gment with binary compression of the argument. The coefficients of the equation { c } nk = 0 can be found using a special ratio for algebraic polynomes . The reached the corresponding polynomes completely classified, choosing optimal from them. It turned out that for each N you can find one set of coefficients { c } nk = 0 ( in fact, there are many equivalent sets, but we are somewhat simplifying the matter here). Now, having the coefficients C K , you need to solve the scalable equation. This turned out to be an extremely difficult task. Together with a colleague in At & T Bell Lab J. Lagaris, she developed a matrix solution - a linear iteration process converging to a certain self -like curve. Thus, the solutions of scaling equations are fractal functions. Accordingly, the finite bursts, except Haarovsky, are fractal functions. They always have limited smoothness at any interval and, therefore, are not expressed through analytical functions. As a result, for each N , a decision ° N was obtained, and from it already the maternal function of bursts ψ n . This function is called- the N-th splash . In the programming literature, it is indicated by DB N. It is concentrated on the segment [0 , 2 N - 1]. The function ψ 1 is the function of the haara. And the function ψ 2 will already be continuous! Recall that Haar is 1909, and ψ 2-1988. Thus, the path from the first to the second surge of reaching lasted 79 years! The smoothness of the bursts increases with the growth of n . A wonderful theorem proven to proven, based on the results of A. Cohen, states that the smoothness of ψ N is not less than 0 , 19 n . Thus, there are bursts of arbitrarily great smoothness! Currently, the exact values ​​of the smoothness indicators are calculated for N ≤ 40.

Speaking of goodshore, one cannot fail to mention another aspect - human. She is an amazing person, this is noted by everyone who dealt with her! I had a chance to meet her in 1998 in Princeton, where the goodshots were a professor of mathematics and headed the signal processing laboratory. At first, I tried to find one of her students to show them their results, but my friends urgently advised to contact her directly. “This is inconvenient,” I objected, “I am a student from Russia, she is a world -famous scientist, probably busy.” In the end, I wrote to her an email, waiting for the answer at best: “Somehow, two weeks, three weeks ...” But the answer came quickly: “Tomorrow at 15:00 is it convenient for you?” Then we met weekly, I tormented it with my results and my terrifying English for 1-2 hours. She listened carefully, wrote down, delved into every little thing. The current correctness and goodwill in relation to me seem implausible to me. At the end of each meeting, she resolutely stopped all my attempts at the apology: “It was very interesting, thanks! Now let's go on Monday, will it be convenient for you? Sorry, I won’t be able to. ”

One philosopher said that with philosophy you need to get sick, but you can’t do this yourself - you can only become infected from another person. I think that many people became infected with the theory of bursts for life.

Vladimir Protasov,
Professor, member-corr. RAS