Saturday, September 29, 2012

Poster creation quick tip

So I have been struggling with creating posters for a conference I am attending next week. The beamer is definitely the way to go but creating a poster in beamer is painful. So here is a work-around.

Create the slides in beamer.  If you have an A0 poster then roughly 16 slides or less
Create a pdf of the slides
Convert pdf to high resolution jpeg images
gs -dNOPAUSE -dBATCH -sDEVICE=jpeg -r2100 -sOutputFile='page-d.jpg' Flyer.pdf

Import these images in Open Office and create a gigantic poster in Open Office.

Thursday, September 6, 2012

Randomized algorithm for Verification of Matrix Multiplication

Suppose you want to verify if AB = C and A is m by n and B is n by k then, the time taken for this is O(mnk + nk) = O(mnk)

What if you had a vector x, then ABx = Cx...  here x is a random vector.
x  is of dimensionality k by 1  and created by randomly sampling from a gaussian distribution.

Now the time taken to compute Bx is O(nk)  and is of dimentionaity n by 1 and time taken to compute ABx is O(mn). Similarly, time taken to compute Cx is O(mk)...

So the total time taken to verify is O(mn+nk+mk) and not O(mnk)