From: [Permission pending]
Subject: Re: Stupid LA Question
To: rusin@math.niu.edu (Dave Rusin)
Date: Thu, 2 Nov 1995 11:23:19 -0700 (MST)

> In article <46qrmo$3jm@schubert.cs.colostate.edu> you write:
> >Is there an extension of Linear Algebra to work
> >on 3D arrays instead of 2D matrices.  How would
> >multiplication, transpose, eigenvalues, etc. be
> >formed.  Question would be to apply a KL compression
> >on a 3D dataset instead of standard 2D.
> 
> They're called _tensors_. The right way to analyze them is not really
> as arrays of numbers, since that would require picking bases, but to
> view them as geometric objects. It's rather a technical subject, well
> suited to certain natural constructs e.g. in physics, but not easy to
> understand when removed from those settings.
> 
> dave
> 
> 
>
Dave, 

Thanks for your reply.  If you have a second, let me explain what
I would like to do.

If I have a large 2D array, I can compress that array using a KL
type compression scheme.  This has been done and works very nicely
not only to make the dataset smaller(less tapes to ship) but also
speeds up data display when simple operations are done on the
array.  I'm specifically talking about an array of sampled data 
(seismic data for oil exploration).  In the 3D sense we have data
sampled by x,y coordinates and time vertically.  A typical dataset
may have 2.5*10^9 samples.  Display is in the 2D sense however.  It
is simply an arbitrary slice through the 3D volume.  If I keep
sufficient eigenvalues in the KL decomposition depending on screen
resolution, I easily gain 60% compression on 2D without affecting
the apparent data display.  The data normally has a large amount of
horizontal continuity in it, making the compression work well.

My idea was to use this in a 3D sense.  However, when doing the KL
compression on individual 2D slices through the 3D volume,   I have
a fear of decoupling the 2D slices(ie, a sample, perhaps a spike, is
transformed correctly on one slice but not on the next.)  These individual
differences could be important between the 2D slices.  If there
was a way to do the compression in 3D and keep all the data coupled,
I think that this could be useful.

From your answer, I get the idea that tensors would not be helpful.  If
this is, in reality, what you believe, I could drop the idea without
spending alot of time researching tensors.  I would be appreciative if
you could give me a short answer of what tensors are good for and if
there is any application to my problem.

Thanks much,
[sig deleted -- djr]

==============================================================================

Date: Thu, 2 Nov 95 15:19:35 CST
From: rusin (Dave Rusin)
To: [Permission pending]
Subject: Re: Stupid LA Question

In article <46qrmo$3jm@schubert.cs.colostate.edu> you write:
>Is there an extension of Linear Algebra to work
>on 3D arrays instead of 2D matrices.  How would
>multiplication, transpose, eigenvalues, etc. be
>formed.  Question would be to apply a KL compression
>on a 3D dataset instead of standard 2D.

OK, now I understand a little better, although I must confess I have
no idea what KL compression means.  But as far as I know, data
compression routines tend not to use the structure of the data as a
_matrix_, rather, it is just treated as an _array_. This is certainly
the case with JPEG encoding, for example -- the array is just broken
down into blocks (usu. 8x8) anyway. So, for example, there is no
particular benefit to having a _square array_ to compress, although
you would need _square matrices_ to compute eigenvalues and so on.
If this compression scheme of which you speak is different in that way,
I must apologize in advance. Otherwise, I think you should abandon
your research into tensors for this purpose.

What the JPEG routine does, essentially, is compute a Fourier transform
of the data within a block. This is a lossless encoding, but cannot
be expected to compress at all unless the data vary smoothly within
the block so that, say, a Huffman code can present the spectral data
more compactly. To gain significant compression, one often chooses simply
to drop the high-frequency data, giving a better compression ratio but
with some loss of initial data.

It appears this is your intent, too -- you are willing to sacrifice all
precision which exceeds the capacity of your display. So what you would
want is a 3D version of a Fourier transform. If you stick with digitzed
data, you find yourself wanting to do a discrete transform, which is
usually done with matrices -- perhaps that why you felt you needed a
3D version of matrices in the first place. But it is probably more
instructive to think about the continuous transforms. These are done
with integrals, and you know that integration can be done on domains
in any number of dimensions.

I can't remember the formulae for a discrete transform offhand but it
should run something like this: given  16^3 numbers  a[i,j,k]  you 
construct another array of  16^3  number with a formula like
b[m,n,p]=(1/4^3)Sum_{i,j,k} w^(mi+nj+pk}a[i,j,k]  where  w  is a 16th root of 
1; repeating the transformation returns the original array. If however
you alter the array  b  before re-transforming to find  a, you will
get an array  a'  a little different from  a. I think the "low-frequency"
terms are not those with  m,n, and  p  large but rather those with
m, n, and  p  divisible by high powers of  2; whichever they are, these
are the ones you most want to retain in order to keep  a'  looking more
like  a.

Of course there are a lot of variants, and there are many successful
compression techniques which can store more information in the same
amount of space I have here suggested and yet which are less blunt than
simply throwing away a large portion of the array  b.  Also you can
adjust the procedure to process larger chunks of data at a time, and so on.

Overall, the best way to summarize what you're doing is to say
you've got a lot of values of a function defined on a three-dimensional 
domain; you are re-presenting the data by storing a presentation of
this function in terms of a different basis, a presentation which may
be more amenable to encoding by standard data-compression techniques.
The keyword now used in such a re-presentation is "wavelet analysis",
which is certainly a hot topic in math research.

I'd be happy to clarify what I've said here, but beyond that I think I'm
at my limit. You might want to repost to sci.math or sci.math.research,
but I know there are also groups comp.compression and comp.compression.research
which are likely to be populated by people who know instinctively how to
do all this.

dave