[SciPy-Dev] Randomized linear algebra functionality

[Touqir Sajed]

I assume you are referring to the linear algebra algorithms in section 4.1
that use their basis construction algorithm and not the graph matching and
matroid optimization algorithms? It seems their results are still the state
of the art. I am fine with implementing them.
I am thinking of the following API changes :

(1) Implement   scipy.linalg.dot_lowrank or scipy.linalg.mult_lowrank
for multiplying a low-rank matrix A with another matrix B. Or just
implement this additional functionality within numpy's dot function and add
a boolean parameter.

(2) Add a boolean parameter "rand" to    scipy.linalg.null_space    to use
the more sophisticated randomized algorithm for null space computation.

(3) Implement   scipy.linalg.rankone_matrix_decomposition   for decomposing
the matrix into a sum of r rank 1 matrices.

All of these algorithms should give performance improvements for low-rank
matrices.

On Sat, Sep 15, 2018 at 2:07 PM Matt Haberland <haberland at ucla.edu> wrote:

> I'd really love to see some of the techniques in:
> https://arxiv.org/pdf/1203.6705.pdf
> implemented!
> Matt
>
> On Sat, Sep 15, 2018 at 12:44 PM, Touqir Sajed <touqir at ualberta.ca> wrote:
>
>> Aha, this implements the exact functionality that I had in mind! Thanks
>> for bringing this up Andreas.
>> Regarding fast JL transformation, there is an existing package in python
>> : https://github.com/michaelmathen/FJLT
>> <https://ml-trckr.com/link/https%3A%2F%2Fgithub.com%2Fmichaelmathen%2FFJLT/ItaYhTc7pvlDqpF6qIPH>
>> .
>>
>> Are there functionalities that the core developers have in mind and can
>> use some help implementing them?
>>
>> On Sat, Sep 15, 2018 at 1:04 PM Andreas Kloeckner <
>> lists at informa.tiker.net> wrote:
>>
>>> Touqir,
>>>
>>> Touqir Sajed <touqir at ualberta.ca> writes:
>>> > There seems to be some interest in implementing randomized linear
>>> algebra
>>> > algorithms such as JL transformation, low-rank approximation, etc as
>>> > written in
>>> https://github.com/scipy/scipy/wiki/GSoC-2018-project-ideas
>>> > <
>>> https://ml-trckr.com/link/https%3A%2F%2Fgithub.com%2Fscipy%2Fscipy%2Fwiki%2FGSoC-2018-project-ideas/cBzmzxqJ6V7Fi58kyipk
>>> >
>>> > . To the best of my knowledge, they are not implemented yet. If there
>>> still
>>> > exists interests I would like to implement the Fast JL transformation
>>> and
>>> > the randomized SVD for low-rank approximation. The pseudo code of Fast
>>> JL
>>> > transformation is given here:
>>> >
>>> https://pdfs.semanticscholar.org/ccf0/1e0375d11df5335b645161b4833e32380d89.pdf
>>> > <
>>> https://ml-trckr.com/link/https%3A%2F%2Fpdfs.semanticscholar.org%2Fccf0%2F1e0375d11df5335b645161b4833e32380d89.pdf/cBzmzxqJ6V7Fi58kyipk
>>> >
>>> > . The randomized SVD is based on https://arxiv.org/pdf/0909.4061.pdf
>>> > <
>>> https://ml-trckr.com/link/https%3A%2F%2Farxiv.org%2Fpdf%2F0909.4061.pdf/cBzmzxqJ6V7Fi58kyipk
>>> >
>>>
>>> scipy.linalg.interpolative is in fact based on randomized linear
>>> algebra. In particular, this function:
>>>
>>>
>>> https://docs.scipy.org/doc/scipy/reference/generated/scipy.linalg.interpolative.svd.html#scipy.linalg.interpolative.svd
>>>
>>> already does implement a randomized SVD with a number of acceleration
>>> bells and whistles.
>>>
>>> Andreas
>>>
>>
>>
>> --
>> Computing Science Master's student at University of Alberta, Canada,
>> specializing in Machine Learning. Website :
>> https://ca.linkedin.com/in/touqir-sajed-6a95b1126
>>
>> _______________________________________________
>> SciPy-Dev mailing list
>> SciPy-Dev at python.org
>> https://mail.python.org/mailman/listinfo/scipy-dev
>>
>>
>
>
> --
> Matt Haberland
> Assistant Adjunct Professor in the Program in Computing
> Department of Mathematics
> 6617A Math Sciences Building, UCLA
> _______________________________________________
> SciPy-Dev mailing list
> SciPy-Dev at python.org
> https://mail.python.org/mailman/listinfo/scipy-dev
>


-- 
Computing Science Master's student at University of Alberta, Canada,
specializing in Machine Learning. Website :
https://ca.linkedin.com/in/touqir-sajed-6a95b1126
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/scipy-dev/attachments/20180915/2677a7ea/attachment.html>