Numerical (multi-)linear algebra is central to many computational methods for complex networks, stochastic processes, machine learning, and numerical solution of PDEs. The matrices (or tensors) encountered in applications are often rank-structured: approximately low-rank, or with low-rank blocks, or low-rank modifications of “simpler” matrices. Identifying and exploiting rank structure is crucial for achieving optimal performance and for making data interpretations feasible by means of the most insightful multi-array representation.
A common example is given by the low-rank approximation of a given matrix, for which the singular value decomposition (SVD) is classically employed. For large dimensions, this approach is unfeasible both in terms of computational costs and memory requirements. This problem is particularly crucial when dealing with the huge amount of data currently processed by data science algorithms. Alternatives have been designed to overcome the SVD drawbacks. These include variants of the Lanczos method and adaptive cross approximation.
Recently, randomized methods have gained traction, being more robust than the aforementioned approaches. They only require a few matrix-vector products, and the acceptance of a failure probability, that can be made arbitrarily small by slightly increasing the cost of the method. The analogous problem for tensors (arrays with more than 2 indices) is much harder. No explicit solution is available for the best approximant (when it exists), as no direct analogue of the SVD is known. For this reason, compression strategies have been proposed over the years.
If a computational problem can be reduced to an easier subproblem by a low-rank correction, often we can solve the simple problem first, and then reconstruct only the difference with the actual solution in the form of a low-rank update. Array structures, in the form of matrix and tensor equations, also naturally stem from the computational treatment of many application problems governed by steady-state or time-dependent partial differential equations, where the array form allows to preserve important structural properties of solutions such as symmetry and definiteness, even at low accuracies.
Low-rank structure plays a crucial role also in many other areas. Network science problems, such as clustering and community detection and the construction of preconditioners for solving network-related linear systems, can also be tackled using low-rank approximation techniques, but little work has been done so far in this direction.
Scientific Committee
- Michele Benzi
- Beatrice Meini
- Valeria Simoncini
Organizing Committee
- Fabio Durastante
- Cecilia Pagliantini
- Davide Palitta
Sponsors
 |  |  |
 |  |
