mapping a 2d delay vector from a 1d vector in numpy

Question

I am trying to generate a 2D vector from a 1D vector where the element is shifted along the row by an increment each row.

i would like my input to look like this:

input:
t = [t1, t2, t3, t4, t5]

out = 
[t5,  0,  0,  0,  0]
[t4, t5,  0,  0,  0]
[t3, t4, t5,  0,  0]
[t2, t3, t4, t5,  0]
[t1, t2, t3, t4, t5]
[ 0, t1, t2, t3, t4]
[ 0,  0, t1, t2, t3]
[ 0,  0,  0, t1, t2]
[ 0,  0,  0,  0, t1]

im unaware of a way to do this without using a for loop, and computational efficieny is important for the task im using this for. Is there a way to do this without a for loop?

this is my code using a for loop:

import numpy as np

t = np.linspace(-3, 3, 7)
z = np.zeros((2*len(t) - 1, len(t)))

diag = np.arange(len(t))
for index, val in enumerate(np.flip(t, 0)):
    z[diag + index, diag] = val

print(z)

user3483203 · Accepted Answer · 2018-07-01T01:24:58.200

What you're asking for here is known as a Toeplitz Matrix, which is:

a matrix in which each descending diagonal from left to right is constant

The one difference is that you want the lower triangle of your matrix.

You happen to be in luck, you can use scipy.linalg.toeplitz to construct your matrix, and then np.tril to access the lower triangle.

import numpy as np
from scipy.linalg import toeplitz

v = np.array([1, 2, 3, 4, 5])
t = np.pad(v[::-1], (0, 4), mode='constant')

Solve the matrix and access the lower triangle:

np.tril(toeplitz(t, v))

And our output!

array([[5, 0, 0, 0, 0],
       [4, 5, 0, 0, 0],
       [3, 4, 5, 0, 0],
       [2, 3, 4, 5, 0],
       [1, 2, 3, 4, 5],
       [0, 1, 2, 3, 4],
       [0, 0, 1, 2, 3],
       [0, 0, 0, 1, 2],
       [0, 0, 0, 0, 1]])

To generalize this method, simply calculate the necessary padding for t from the shape of v:

v = # any one dimension array
t = np.pad(v[::-1], (0, v.shape[0]-1), mode='constant')

score 1 · Answer 2 · answered Jul 01 '18 at 00:29

Not aware of a non-loopy method, but you could probably speed this up a bit with roll and column_stack.

v = np.array([1, 2, 3, 4, 5])
t = np.pad(v[::-1], (0, 4), mode='constant')

np.column_stack([np.roll(t, i) for i in range(len(v))]) 
array([[5, 0, 0, 0, 0],
       [4, 5, 0, 0, 0],
       [3, 4, 5, 0, 0],
       [2, 3, 4, 5, 0],
       [1, 2, 3, 4, 5],
       [0, 1, 2, 3, 4],
       [0, 0, 1, 2, 3],
       [0, 0, 0, 1, 2],
       [0, 0, 0, 0, 1]])

score 1 · Answer 3 · answered Jul 01 '18 at 11:11

Here's one vectorized way leveraging strides-tricks that simply uses a view into a zeros-padded array and being a view its memory efficient and hence performant -

def map2D(a):
    n = len(a)
    p = np.zeros(n-1,dtype=a.dtype)
    a_ext = np.r_[p,a,p]
    s0 = a_ext.strides[0]
    strided = np.lib.stride_tricks.as_strided
    return strided(a_ext[-n:], (len(a_ext)-n+1,n), (-s0,s0), writeable=False)

Sample run -

In [81]: a = np.array([2,5,6,7,9])

In [82]: map2D(a)
Out[82]: 
array([[9, 0, 0, 0, 0],
       [7, 9, 0, 0, 0],
       [6, 7, 9, 0, 0],
       [5, 6, 7, 9, 0],
       [2, 5, 6, 7, 9],
       [0, 2, 5, 6, 7],
       [0, 0, 2, 5, 6],
       [0, 0, 0, 2, 5],
       [0, 0, 0, 0, 2]])

If you need the output to have its own memory space, use .copy()

Timings on 5k elements array -

In [83]: a = np.random.randint(0,9,(5000))

# From this post's soln
In [84]: %timeit map2D(a)
10000 loops, best of 3: 26.3 µs per loop

# If you need output with its own memory space
In [97]: %timeit map2D(a).copy()
10 loops, best of 3: 43.6 ms per loop

# @user3483203's soln
In [87]: %%timeit
    ...: t = np.pad(a[::-1], (0, len(a)-1), mode='constant')
    ...: out = np.tril(toeplitz(t, a))
1 loop, best of 3: 264 ms per loop

# @coldspeed's soln
In [89]: %%timeit
    ...: t = np.pad(a[::-1], (0, len(a)-1), mode='constant')
    ...: out = np.column_stack([np.roll(t, i) for i in range(len(a))])
1 loop, best of 3: 336 ms per loop

mapping a 2d delay vector from a 1d vector in numpy

3 Answers3