EXPIR.TXT  in /proj  *Fei PC      May 11th, 1993  


  On the role of experiments in numerical (harmonic) analysis: 

  Since  "Numerical Harmonic Analysis", which this subproject
  represents, is a rather new branch of mathematics
  (and different people might have divergent
  opinions and ideas about such a field) we would like to give some expla-
  nations concerning OUR understanding of EXPERIMENTAL MATHEMATICS as
  well as Numerical Mathematics with respect to applications in signal
  analysis, specifically to IA = image analysis. 
  
  1)  Experiments and numerical analysis:
  Being mathematicians we firmly believe that good theoretical foundations
  are important in order to obtain efficient algorithms.
  Having a good/sound theoretical foundation means for us not just to have
  a complicated abstract machinery (this may happen, but is never the aim),
  but much more to have clear concepts and well-defined assumptions.
  Theoretical considerations help to make use the mathematical structure of 
  the problem. It has often been discussed whether mathematical research
  leads to discoveries or inventions, and we would say that both aspects
  have their arguments. Very often the DISCOVERY of some 
  of up to that moment unrevealed structural background
  can be used the INVENT a good algorithm on that basis. 

  Experimental work may be used to make such discoveries, to test whether 
  a given algorithm applies to situations, for which no theory is yet 
  available, to find combinations of known algorithms to extend the range
  of problems that can be attacked. This initial phase of experimental works
  helps to identify certain phenomena, to form conjectures, which then are
  considered from a theoretical point of view, where the general ideas have
  to be worked out. Insight on this level will than lead to convergence proofs
  (preferably with convergence rates that can be guaranteed in advance).

  It follows the Numerical implementation (which may take some time, and 
  only the use of MATLAB helps us to keep the time for testing a large 
  number of methods within a reasonable time), which allows to make 
  systematic tests on the basis of theoretical work. 

  Of course developement goes in circles, the barriers found for a given
  algorithm or lack of speed are taken as a reason to improve theory, to
  modify the algorithm, and questions that come up (are certain conjectures
  reasonable, is it possible to find counterexamples?) in theoretical 
  question are often inspiration for new experiments. Never one side (just
  fast implementation, or only theoretical consideration and possibilities
  to perform the algorithms which are described in theory) alone is 
  the sole goal of our work. Experience so far, both within our group,
  and through the cooperation with colleagues more active on the pure or
  the applied side, have been very encouraging and make us very optimistic
  that further good scientific results can be obtained based on this approach.
  
  2) Experiments and documentation.
  If one thinks of experiments the basic tool of physics to gain
  insight into the nature of materials, or electricity, it has been always be
  driven by the aim of better "understanding" certain effects, and the wish 
  for insight into the structure of the cosmos, or certain forces (magnetic,
  gravity, electric,...). As one of the main principles the possibility of
  verification or repetition of experiments has been established: Given a 
  careful description of the setup and the basic constants for the experiment
  "in principle" any physicist having the appropriate equipment should be 
  able to repeat the experiment, to compare his observations with those 
  described in a publication about such experiments, and usually will come
  up with the same conclusions. 
  
  It appears to us (maybe because we have not been too long exposed to the
  field) that in some branches of signal analysis such requirements are not
  the applied in the expected way. 
  Maybe some engineers are too busy to make certain things
  happen, so that they do not find time to care for a good documentation.
  However, sometimes also papers are just understood as a presentation 
  of some observations on a specific example, although the implicit claim
  (the impression the paper wants to give) seems to be to make statements
  of a general nature (i.e. comparison of different algorithms). 
  With respect to the above mentioned standards 
  we found quite often that the data on which published experiments
  are based are not available (not even to the author 2 years after the 
  publication of the paper, a typical reason for that being that
  the student has "left the university").

  Based on MATLAB we have developed a documentation toolbox which we can
  use to prevent situations as described above. This also allows us to come
  back to certain standard examples in case a new algorithm, or a new variant
  of an old algorithm (all of the quickly implemented in MATLAB) has to be 
  compared in his performance to an earlier one. 
 
  3) Experiments and Theory:
  It is natural to ask, if a given algorithm behaves in practice in the same
  way as "in theory". If theory is correct, we can rather hope that this is
  NOT the case, because we might have much better performance of certain 
  algorithms than predicted from theory. We have found such a situation with
  the Voronoi reconstruction method (cf. "Theory and practice of irreg. 
  sampling", Part II), where practical performance is beating the corresponding
  method with piecewise linear interpolation (=PLN). Theory seemed to 
  indicate that PLN has to be better (which also appears quite plausible, 
  because it is more "sophisiticated" than piecewise constant continutation).
  However, practical experiments showed that the converse is true. As a matter
  of fact the behavior of PLN appears to be close to that of theoretical
  performance of PLN (which is better than theoretical performance of the
  Voronoi method). HOWEVER, in practice, the VOR-Methods is MORE efficient,
  in some cases even substantially.    
  
  This fact raises immediately theoretical questions (which we hope to 
  approach in the upcoming project):
   a) will it be possible to improve the statements concerning VOR?
   b) is it always true that VOR behaves better than PLN? 
     or is it just a statistical questions: "most often"  
         (or only in the average)
      VOR is better  than PLN by xx %. 
      Obviously such questions lead very quickly to statistical questions,
      which we do not want to pursue here further. 

  Finally, experiments have both the role to confirm the validity of
  theoretical statements (e.g. to see how detailed theory is describing
  the actual "world" of algorithms), or to obtain observations, which 
  may lead to improvments of known algorithms, and sometimes even completely
  new approaches. 
  Sometimes also theory has to do the unpleasant job of giving hints as to
  what the maximal speed ("optimal rate of convergence") at which convergence
  can take place in some of the iterative algorithms. 
  
  
  4) Proofs and Practice:
  Among scientist from applied fields or technical sciences the necessity of 
  having  "proofs"  is often considered as unimportant. Algorithms are applied
  as long as "reasonable" results come out, "continuous" models are taken as 
  a justification for a "discrete" algorithm, and conversely the success of
  a discrete algorithm is taken as indication that an often only heuristically
  presented continuous theory is "true". Of course, there are usually strong
  ties between the two sides of maybe one single theoretical phenomenon, but
  strictly speaking only analogies (which cannot be used to derive any
  definite guarantee) are at work. 
  
  The role of "mathematical proofs" is therefore more than one of a worst case
  analysis, a guarantee that can be given in advance (e.g. about the speed of
  convergence of some reconstrucion algorithm, if applied to a situation of a
  certain "quality", such as maximal gap size as compared to the Nyquist rate).
  
  5) Experiments and Resource
  Practical experminents may very well depend on the means one has available
  e.g. the type of computer available, and the possible degree of parallelism 
  on such machines. Furthermore, the storage (memory) requirements of similar
  algorithms might have quite different requirements as far as main memory
  (to hold intermediate results in memory, for example) are concerned, for
  example. 
   
  6) already mentioned in 1): Numerical work , implementation of
  algorithms, experimental work are three different topics, and we 
  are not restricting our attention to one of them, actually integration
  of all three aspects with theoretical aspects ("nothing Is more efficient
  than a good theory") is our main goal.  

   Hans G. Feichtinger.  Head of  NUMERICAL HARMONIC ANALYSIS GROUP
   Math.Dept., Univ. Vienna  

   *********************************************************************    
   H.G.FEICHTINGER             ANONYMOUS  FTP: 131.130.22.36                
   UNIVERSITY OF VIENNA                   FEI@TYCHE.MAT.UNIVIE.AC.AT        
   DEPARTMENT OF MATHEMATICS              A8131DAN@HELIOS.UNIVIE.AC.AT        
   STRUDLHOFGASSE 4                       A8131DAN@AWIUNI11.BITNET  
   A-1090 VIENNA / WIEN                   TEL:  ++43-1-4088311/4            
   AUSTRIA                    ALTERNATIVE>TEL:  ++43-1-31367/4000 (SECR)    
   -------------------------------------- FAX:  ++43-1-4088311-5 -------