-bb_ t1_ir73phc wrote
Last month I've tried for fun the very similar thing (but on the smaller scale (3x3 @ 3x3) and with a different approach), and only when I read this paper I've realized, that there are already algorithms for exact same thing I've tried :c We can represent each entry in 3x3 matricies with a letter and there are only 81 possible combinations of 2 characters from the first two matrices, such that they are from different matrices. These pairs will represent multiplications. So I decided that I'll have a unique slot for each of them in the vector of len 81. Then you need to create several pairs of sums of single characters (each sum consists of elements from one matrix). Sums in pairs will be multiplied, and the result of this multiplication can be represented as a vector mentioned earlier. We can also represent each cell in the resulting matrix as a vector. So if we create enough pairs, we will just need to solve L0-regularized linear system AX = b, where A is stacked vectors of sums, b vectors from resulting matrix (I hoped I can solve it by just using Lasso (because L1 is sort of approximating L0) and it will choose only suitable components). Note that this system without regularization will have infinitely many solutions: A is 81 x #(pairs of sums), X is #(pairs of sums) x 9, b is 81 x 9. And solution will be better than Strassen's algo if ||X.sum(-1)||_L0 / 27 < 7/8 (because Strassen's algo replaces 8 multiplications with 7) and now, when I finally read the paper I also know that it should be better than Laderman's one, so ||X.sum(-1)||_L0 / 27 < 23/27.
Viewing a single comment thread. View all comments