Creating Synthetic Data Using the Fast Fourier Transform

This question was recently asked on the Quantitative Finance forum and one answerer's link to here piqued my interest. My comments to said answer were
"Interesting link! I theorise that one way it could be done is to apply a Fast Fourier Transform (e.g. FFT function in Octave/MATLAB) to the original series, then divide the resulting vector into segments and within each separate segment randomly permute the values, and finally reconstruct the time series by applying the Inverse Fast Fourier Transform (IFFT function). By randomly permuting the values you will not alter the amplitudes of the composite sine waves but will slightly alter their periodicity - this will naturally tend to restrict the range of the new series to that of the original."
and
"This is such an intriguing approach that I may "knock up" some Octave code on my blog and post a link to it from here."
This blog post is my attempt to "knock up" the Octave code.

The "guts" of the code are a .oct function that randomly permutes the FFT output vector that is given to it as its only input argument and the C++ code for this .oct function is given below.
Note: due to formatting issues the headers are not correctly displayed; the octave headers should be enclosed between a "<" and ">" after the #include.

#include octave/oct.h
#include octave/dColVector.h
#include octave/CNDArray.h
#include "MersenneTwister.h"
     
DEFUN_DLD (permute_vector, args, , "Input is a vector that is to be permuted once")
{
octave_value_list retval;

int nargin = args.length () ;
int vec_length = args(0).length () ;

// check the input arguments
    if ( nargin > 1 )
    {
        error ("Invalid arguments. Input is a vector that is to be permuted once") ;
        return retval ;
    }
    
    if (vec_length < 2 )
    {
        error ("Invalid arguments. Input is a vector that is to be permuted once") ;
        return retval ;
    }
    
    if (error_state)
    {
        error ("Invalid arguments. Input is a vector that is to be permuted once") ;
        return retval ;
    }
// end of input checking

 ComplexNDArray input_vector = args(0).complex_array_value () ;
 ComplexNDArray output_vector = args(0).complex_array_value () ;
 int k1;
 int k2;
 
 MTRand mtrand1; // Declare the Mersenne Twister Class - will seed from system time

       k1 = vec_length - 1; // initialise prior to shuffling the vector

       while (k1 > 0) // While at least 2 left to shuffle
             {          
             k2 = mtrand1.randInt( k1 ); // Pick an int from 0 through k1 

               if (k2 > k1) // check if random vector index no. k2 is > than max vector index - should never happen 
                  {
                  k2 = k1 - 1; // But this is cheap insurance against disaster if it does happen
                  }

             output_vector(k1) = input_vector(k2) ; // allocate random pick k2 from input_vector to the k1 vector index of output_vector
             input_vector(k2) = input_vector(k1) ; // replace random pick k2 content of input_vector with content k1 of input_vector
             k1 = k1 - 1; // count down 
             } // Shuffling is complete when this while loop exits

 retval(0) = output_vector ; 
 
return retval; // Return the output to Octave
} 

The Octave script that calls the above function is

clear all

contract = input( "Enter contract symbol e.g. sp: ","s") ;
data = load("-ascii",contract) ;
n = rows(data)
index_begin = input( "Enter index_begin: ") ;
index_end = input( "Enter index_end, value not greater than n: ") ;

close = data(index_begin:index_end,7) ;

% detrend the close vector prior to applying the fft
slope = ( close(end) - close(1) ) / ( length(close) - 1 ) ;
v1 = (0:1:length(close)-1)' ;
detrended_close = close .- ( v1 .* slope ) ;
close_index_begin = close(1)
detrended_close_index_begin = detrended_close(1)
detrended_close_index_end = detrended_close(end)

% create zero padded vector for fft
L2 = 2^nextpow2( length(close) ) ; half_L2 = L2/2 ;
y2 = zeros( 1,L2 ) ; y2( 1:length(close) ) = detrended_close ;

% apply the fft
transform = fft( y2 ) ;

% permute the first half of the transform vector in "chunks" of 10
max_ii_value = floor( half_L2 / 10 ) ;
for ii = 1:max_ii_value
transform( (ii*10):(ii*10)+9 ) = permute_vector( transform( (ii*10):(ii*10)+9 ) ) ;
endfor

% take the inverse fft
ifft_vec = real( ifft( transform ) ) ;

% retrend the ifft_permuted_vec
retrended_ifft_vec = ifft_vec( 1:length(close) )' .+ ( v1 .* slope ) ;

% statistics
correl = corrcoef (close, retrended_ifft_vec)
spear = spearman (close, retrended_ifft_vec)
tau = kendall (close, retrended_ifft_vec)

plot( close,'b',retrended_ifft_vec,'r' ) ; legend( 'close','permute' ) ; 

This script could undoubtedly be made more efficient by putting the for loop on lines 28 to 30 within the .oct function itself, but this is just a proof of concept. The script allows one to extract any contiguous section of data by use of the index_begin and index_end inputs or, of course, to select the whole data range. Some simple statistics are calculated using in-built Octave functions and can be seen in the terminal windows in the screen shots. Finally the script plots the original input data along with the FFT permuted output data. Typical screen shots are shown below, with the original data in blue and the FFT permuted data in red.

All S&P data

The last few years of the above

The same last few years indexed using the index_begin and index_end method to apply the function just to these years and not the whole data set

The close_index_begin, detrended_close_index_begin and detrended_close_index_end values also seen in the terminal windows are a simple sanity check to see that the original data has been detrended correctly prior to performing the FFT.

Trading Rules, Aphorisms & Books

An interesting link.

The Perfect Oscillator on S&P E-Mini Data

Following on from my previous posts the chart below is a snapshot of the last 150 days of the S&P E-mini continuous futures contract, up to and including the 9th December.

The top pane is obviously a plot of price showing triangles to indicate cyclic highs and lows when the Perfect Oscillator (middle pane) crosses its SMA (see previous post for explanation). As explained earlier the algorithm used in calculating the PO makes use of projected/predicted prices, and since these "forward prices" are available from the .oct function the bars are coloured according to the 5 and 10 day "forward prices." Based on a very simple if/or statement in the code essentially we should be long when the bars are blue and short when red. The few whites bars that are visible are bars where the conditions for being blue or red are not met.

Superimposed over the middle pane plot of the PO are the full period EMA and plus and minus 1 exponential standard deviation lines, a sort of Bollinger Bands over the indicator. The bottom plot is of the bandpass indicator which is used in the "forward prices" algorithm.

Based on the logic and theory of the PO the rules for use are essentially:-
1) go long/short according to the PO SMA crossings
2) confirm the above by the bar colours
3) exit/close up stops when the PO crosses its exponential standard deviation lines

and based on these simple rules a short entry is indicated for 12th December, particularly since the bandpass is also indicating a short trade with its leading function cross. Will be interesting to see how this indicated trade works out.

Update #2 on Perfect Moving Average and Oscillator

Below are screenshots of the PMA and PO based upon the improved price projection algorithm discussed in the previous post, shown on an idealised time series of a sinewave (plus trend) in cyan in all screenshots.

The first 3 are plots of the 10 bar PMA in red with a normal 10 bar EMA in green shown for comparative purposes.

As the theory suggests it can be seen that the PMA has the equivalent smoothing of the 10 bar EMA but without any lag.

The next series of screenshots are of the PO, where again the "price" is cyan, the various red lines are 2 bar, 3 bar etc. POs up to an 11 bar PO, and the green PO is a simple average of all these POs.

As I had anticipated these POs lead price by a quarter period which means the cycle highs and lows are indicated by the green "average PO" crossing its centre line, which in turn is a full cycle period length simple moving average of the average PO. My leading oscillator indicator should give timely warnings of these upcoming turns in price. It is also interesting to note that the individual, longer length PO crossings (greater amplitude) also give advance warning of the upcoming turn and the fact that the shorter length POs NOT crossing the centre line and being entirely above or below said centre line seem to indicate the strength of any trend.

Update on the Perfect Moving Average and Oscillator

It has been some time since my last post and the reason for this was, in large part, due to my changing over from an Ubuntu to a Kubuntu OS and the resultant teething problems etc. However, all that is over so now I return to the Perfect Moving Average (PMA) and the Perfect Oscillator (PO).

In my previous post I stated that I would show these on real world data, but before doing this there was one thing I wanted to investigate - the accuracy of the price projection algorithm upon which the average and oscillator calculations are based. Below are four sample screenshots of these investigations.

Sideways Market

Up Trending Market

Down Trending Market

The charts show a simulated "ideal" time series (cyan) with two projected price series of 10 points each (red and green) plotted such that the red and green projections are plotted concurrently with the actual series points they are projections, or predictions, of. Both projections/predictions start at the point at which the red "emerges" from the actual series. As can be seen the green projection/prediction is much more accurate than the red, and the green is the improved projection algorithm I have recently been working on.

As a result of this improvement and due to the nature of the internal calculations I expect that the PMA will follow prices much closer and that the PO will lead prices by a quarter cycle compared with my initial price projection algorithm. More on this in the next post.

The Theoretically Perfect Moving Average and Oscillator

Readers of this blog will probably have noticed that I am partial to using concepts from digital signal processing in the development of my trading system. Recently I "rediscovered" this PDF, written by Tim Tillson, on Google Docs, which has a great opening introduction:

" 'Digital filtering includes the process of smoothing, predicting, differentiating,

integrating, separation of signals, and removal of noise from a signal. Thus many people
who do such things are actually using digital filters without realizing that they are; being
unacquainted with the theory, they neither understand what they have done nor the
possibilities of what they might have done.'

This quote from R. W. Hamming applies to the vast majority of indicators in technical
analysis."

The purpose of this blog post is to outline my recent work in applying some of the principles discussed in the linked PDF.

Long time readers of this blog may remember that back in April this year I abandoned work I was doing on the AFIRMA trend line because I was dissatisfied with the results. The code for this required projecting prices forward using my leading signal code, and I now find that I can reuse the bulk of this code to create a theoretically perfect moving average and oscillator. I have projected prices forward by 10 bars and then taken the average of the forwards and backwards exponential moving averages, as per the linked PDF, to create a series of averages that theoretically are in phase with the underlying price, and then taken the mean of all these averages to produce my "perfect" moving average. Similarly, I have done the same to create a "perfect" oscillator and the results are shown in the images below.
Sideways Market

Trending up Market

Trending down Market

The upper panes show "price" and its perfect moving average, the middle panes show the perfect oscillator, its one bar leading signal, and exponential standard deviation bands set at 1 standard deviation above and below an exponential moving average of the oscillator. The lower panes show the %B indicator of the oscillator within the bands, offset so that the exponential standard deviation bands are at 1 and -1 levels.

Even cursory examination of many charts such as these shows the efficacy of the signals generated by the crossovers of price with its moving average, the oscillator with its leading signal and the %B indicator crossing the 1 and -1 levels, when applied to idealised data. My next post will discuss the application to real price series.

Post to TradingBlox Forum

I have recently posted a reply to a thread on the TradingBlox forum here which readers of this blog might be interested in. The Octave code below is that used to generate the graphic in the linked forum reply.

clear all

a_returns = [2,-1,2,-1,2,-1,2,-1,2,-1];
b_returns = [3,-1.5,3,-1.5,3,-1.5,3,-1.5,3,-1.5];
c_returns = shift(b_returns,1);

a_equity = cumsum([1,a_returns]);
b_equity = cumsum([1,b_returns]);
c_equity = cumsum([1,c_returns]);

ab_equity = a_equity .+ b_equity;
ac_equity = a_equity .+ c_equity;

ab_equity_correl = corrcoef(a_equity,b_equity)
ac_equity_correl = corrcoef(a_equity,c_equity)

ab_returns_correl = corrcoef(a_returns,b_returns)
ac_returns_correl = corrcoef(a_returns,c_returns)

ab_centre_returns_correl = corrcoef(center(a_returns),center(b_returns))
ac_centre_returns_correl = corrcoef(center(a_returns),center(c_returns))

plot(a_equity,"k",b_equity,"b",c_equity,"c",ab_equity,"r",ac_equity,"g")
legend("a equity","b equity","c equity","ab equity","ac equity")