Student research projects at Scientific Computing Group¶
Contact: Prof. Ivan Oseledets, i.oseledets@skoltech.ru, joint with the group members.
Below is the list of projects. Some of them can later evolve into the master theses. They can be also taken by a group of students (23).
Prerequisites¶
The main prerequisite is the motivation work with us: our group is big, and we are always quite helpful, even if you are not a master in the particular topic. However it is a good idea that you know linear algebra (or at least learning it). For machinelearning related projects, machine learning experience is a good idea, for PDErelated it not bad to have a basic knowledge about finite differences and/or finite elements. Many projects are related to tensor train and quantized tensor train decompositions: this is our “special feature”, which you will surely need to learn. Also, all the projects are related to programming and Python is the preferred language.
Tasks¶
The tasks are of course specific for the particular projects, however the pipeline is similar.

Do a literature survey. Google Scholar will help you. Read all the papers you can find on the topic, not only the particular ones that the advisor has given to you. Follow the references in the papers, find keywords, define key ideas.

Find appropriate software and baseline algorithm. Typically, you are not the one solving a particular problem: look for the same projects, what was their approach and try to identify possible improvements

Start writing in \(\LaTeX\) a short summary of what you are doing (something like a journal)

Try to formulate questions: a good question is the core to the answer.

Ask the questions to me or group members.

Write code, do experiments, get new results (or find that the approach is not working at all  this is also a scientific result).
List of projects¶
 Deep PDE: Try to solve PDEs using deep learning
 Multiclassifier: Learn many linear classifiers with lowrank tensor constraints
 Linear classification: Linear classification with many classes & lowrank optimization: Given a machine learning task with huge number of classes, try to reduce the complexity by incorporating lowrank constraints into the problem.
 Maxvol feature selection: Given machine learning task with many features, try to extract the “good” ones using maximumvolume algorithm
 Risk analysis and highdimensional integrals: Using recently developed fast lowrank numerical quadrature technique, evaluate integrals over Brownian motion and apply to
 Sumproductnetwork and Metropolis algorithm: Given a multivariate function, try to recover sumproduct network for it based on Metropolis sampling method.
 Fast direct solver for sparse matrices: Block elimination for hierarchically semiseparable matrices
 Boltzmann collision integral: Implement (possibly find a new one) fast technique for the evaluation of the Boltzmann collision integrals.
 Parallel tensortrain optimization: using message passing algorithm and its connection to loopy belief propagation.
 Finite element solver for topology optimization in 3D printing:. Study different regularization techniques for the finite element (FEM) solvers for topology optimization of different shapes.
 TTcross approximation for topology optimization in 3D printing:. Given a “Legotype structure” of a 3D topology, defined by a set of parameters, apply & compute TTcross approximation of the optimized quantity.
 Quantized tensor train solver topology optimization in 3D printing: Develop a QTT solver for shape & topology optimization for different computational 3D printing tasks.
 Optimal sparse grids: Given a set of multivariate functions, find the best interpolation points using maxvol algorithm.
 QTTfun project: Develop a QTT alternative to the Chebfun system.
 TTToolbox production: Develop a welldocumented, clean codebase for the TTToolbox project.
 Tensors on GPU: Develop a prototype code for the TTToolbox on GPU (OpenCL).
 Tensors on MPI: Develop a prototype code for the TTToolbox on a parallel cluster (MPI).
 Volume integral equation solvers using QTT: Given a volume integral equation, develop an efficient QTTsolver for it.
 Logistic matrix factorization using Riemannian optimization: In many problems, instead of the Frobenious norm, other loss functionals are used.
Deep PDE¶
Deep learning is now extremely popular for many different tasks, including image processing, speech recognition and many others. On the other hand, PDEs require a lot of computing power. The goal of this project is to study the applicability of deep learning methods (based on standard software) to approximate the functionals of solution of PDEs.
Problem description.¶
Consider a thermal conductivity problem
where \(k\) is a given coefficient. Then we want to approximate the functional \(F(u)\) of the solution (i.e., maximal temperature, mean temperature). The goal is to design a neural network that will be able to approximate this quantity to sufficient accuracy.
Tasks.¶
 Learn how to solve thermal conductivity problem numerically
 Create a database of solutions/values of the functional
 Design a deep architecture capable of approximating the functional.
Multiclassifier¶
Problem description.¶
We propose the following classifier. Given a feature vector \(p\), the classification is performed by the selection of the path \(i_1, \ldots, i_d\) that maximizes the “softmax” criteria [ F(p, i_1, \ldots, i_d) = \frac{p W_1(i_1) \ldots W_d(i_d)}{ p W_1(i_1) \ldots W_{d1}(i_{d1}) W}, ] where \(W_d = \sum_{i_d = 1}^c W_d(i_d)\) and the last variable \(i_d\) is the class variable (which we want to discover). The learning of the matrices \(W_k(i_k)\) can be done by a gradientdescent type algorithm: for each training sample \((p_s, c_s)\) given \(W\) we update the best path \(i^{(s)}_1, \ldots, i^{(s)}_{d1}\) by maximizing the classification, and then for a given set \((p_s, i_1, \ldots, i_d)\) we minimize the loss (for example, logistic regression on the softmax criteria, or just the softmax itself) by taking a Riemanian gradient descent.
This can be viewed as a \textbf{multiple linear classificator}, but with a special structure of the classificator matrices, otherwise the overfitting would be obvious. For small number of layers the inference the classification would not be hard (i.e. \(10\) layers each of size \(2\)).
It is also close to the highway networks.
Tasks.¶
 Get familiar with logistic regression
 Get familiar with Riemannian optimization
 Get familar with TTToolbox
 Implement the multiclassifier approach
Linear classification¶
Problem description.¶
A typical linear regression uses the following classifier. Given a feature vector \(x\) and number of classes \(c\), we learn an \(F \times C\) weight matrix \(W\) and the probabilities for different classes are given by the vector
where \(Z\) is the normalization constant. For large number of features and large number of classes (maybe infinite, when the class variable is continious), storing matrix \(W\) is difficult, and we propose to constraint it to the rank\(r\) case.
Tasks.¶
 Get familiar with rank\(r\) matrices
 Get familiar with Riemannian optimization over rank\(r\) manifolds
 Find a good problem with many classes
 Test the method!
Maxvol feature selection¶
Problem description.¶
A machine learning task with many features can be difficult to solve; however, many features are not so important, and only important features can be used for learning larger and more accurate classifiers. But how to select those features? The idea that we want to test is based on the maximal volume submatrices. Represent the data as \(N_{obj} \times N_F\), and find there the submatrix with maximal determinant.
Tasks.¶
 Look for different feature selection algorithms in the literature
 Find appropriate manyfeatures datasets
 Implement the maximal volume submatrix approach (see, for example, https://bitbucket.org/muxas/rect_maxvol)
Risk analysis and highdimensional integrals¶
Problem description.¶
Many stock prices can modelled using Brownian motion, i.e. the next state depends on the previous state plus some random event. Important statistical options (for example, option calls) can be then estimated as expectations of random process. The straightforward way is to do MonteCarlo simulation, but it can not give high accuracy. Another way is to write down the expectation as a path integral and then approximate it by a multidimensional integral. For similar integrals we have recently developed a new technique, http://arxiv.org/abs/1504.06149. The idea is to test it for examples from risk analysis.
Tasks.¶
 Read the papers on highdimensional integrals in risk analysis
 Read the paper http://arxiv.org/abs/1504.06149
 Implement the code from http://arxiv.org/abs/1504.06149 for highdimensional financial integrals
Sumproductnetwork and Metropolis algorithm¶
Problem description.¶
Sumproductnetworks is a new deep architecture. One of its interesting property is that there a constructive algorithm for learning the structure of such network from the observations. On the other hand, one can look at SPN as an approximation of multivariate functions. The idea is then to use Metropolistype algorithm that samples the given function as it was the probability density, and then apply the SPN learning to recover the SPN structure.
Tasks.¶
 Read literature about sumproductnetworks
 Get familiar with software that learns the network structure
 Get familiar with the Metropolis sampling algorithm
 Try to compute SPN for deterministic functions
Fast direct solver for sparse matrices¶
Problem description.¶
Sparse matrices are important and have \(\mathcal{O}(N)\) parameters. However solving a linear system is much more difficult. The goal of this project is to get familiar with the subject, and implement the fast direct solver based on socalled HSS structure.
Tasks.¶
 Read literature on fast lowrank direct solvers
 Study our code
 Implement a variant for HSS structure
Boltzmann collision integral¶
Problem description.¶
Boltzmann collission integral is an integral transform that takes two functions from \(L^2(\mathbb{R}^3)\) to a one function in \(L^2(\mathbb{R}^3)\). For example, see http://www.sam.math.ethz.ch/sam_reports/reports_final/reports2012/201228.pdf. Discretizated on a grid, it can be defined as a \(N^3 \times N^3 \times N^3\) array, and evaluation requires \(\mathcal{O}(N^9)\) complexity. However, it has many symmetries. Our goal is to compare different method for the evaluation of the Boltzmann integral.
Tasks.¶
 Read the literature for numerical evaluation of Boltzmann collision integrals
 Come up with the discretization scheme
 Implement it and evaluate its efficiency
Parallel tensortrain optimization¶
Problem description.¶
TTformat (Tensor Train) is a representation of \(d\)dimensional tensors of the form
where \(G_k(i_k)\) has size \(r_{k1} \times r_k\) for fixed \(i_k\). A typical task to find the TTrepresentation is to optimize over the cores \(G_k\) in a sequential manner (all fixed, update one and so on). Our goal is to present an asynchonous versions of such algorithm, based on the connection with loopy belief propagation
Tasks.¶
 Get familiar with tensor trains
 Get familiar with loopy belief propagation
 Implement an asynchonous optimization for TTfromat and study its efficiency.
Finite element solver for topology optimization in 3D printing¶
Problem description.¶
The “megagoal” is given a functional \(F\) find a topology that optimizes this functional given some constaints (weight of the structure, for example). One of the typical task is linear elasticity, and it is being solved by iteration over the material properties. One can formulate the problem as a minimization problem with constraints (regularization).
Tasks.¶
 Get familiar with FEM approaches for topology optimization
 Select an appropriate topology optimization problem
 Formulate it as an inverse problem with a suitable regularization
 Implement a prototype code
 (Bonus) Print the structure
TTcross approximation for topology optimization in 3D printing¶
Problem description.¶
The “megagoal” is given a functional \(F\) find a topology that optimizes this functional given some constaints (for example, weight of the structure). One of the ways to do so is to use “ball and sticks” method to create the structure: a set of primitives that can be connected in different ways and also parametrized with several parameters. Checking all possible parameters has exponential complexity, and each computation requires a solution of a PDE. The idea is to use TTcross method to adaptively sample the parameter space.
Tasks.¶
 Get familiar with FEM approaches for topology optimization
 Select a suitable local model, determine the number of parameters
 Get familar with TTcross approximation algorithm
 Write a prototype code
Quantized tensor train solver topology optimization in 3D printing¶
Problem description.¶
The “megagoal” is given a functional \(F\) find a topology that optimizes this functional given some constaints (weights). One of the typical task is linear elasticity, and it is being solved by iteration over the material properties. One can formulate the problem as a minimization problem with constraints (regularization). Our goal here is to use the weirdest regularization: contraint the material properties to lowQTT rank case. However, you can be smarter, and come up with other ideas, for example coming from deep networks as well (that would allow for very curved shapes to be generated). However to work on this project you should get familiar both with the FEM solvers for a topology optimization codes, and with optimization with lowrank constraints.
Tasks.¶
 Get familiar with FEM approaches for topology optimization
 Get familiar with TensorTrain optimization
 Try to apply TT/QTT contraints to the material coefficients to get new optimized shapes.
Optimal sparse grids¶
Problem description.¶
Approximation of multivariate functions is a notoriously difficult tasks. One of the most efficient approaches, based on socalled sparse grids is based on using the set polynomials with bounded total degree. This provides a sparse basis set in the set of multidimensional functions. Interpolation is the simplest task, and in the standard setting gives rise to the socalled sparse grids. However, given the basis, the problem of selecting optimal interpolation points can be solved by the maximum volume algorithm=. The goal of this project is to compute those interpolation sets and evaluate their efficiency.
Tasks.¶
 Get familiar with sparse grids
 Get familiar with maxvol algorithm
 Implement a functional version of the maxvol algorithm
 Estimate the efficiency of the approach
QTTfun project¶
Problem description.¶
QTT (Quantized Tensor Train) is a very elegant & efficient representation of functions, which in many cases allows to achieve complexity logarithmic in the number of samples. However, even for 1dfunctions using the basic software (http://github.com/oseledets/ttpy) it is not that straightforward to compute integrals, find roots. This is all implemented in the Chebfun system in a very nice and lucrative way. The goal of this project is implement a QTT alternative to the Chebfun project, and it should be much more efficient.
Tasks.¶
 Get familiar with tensor train/QTT. Install the basic software
 Get familiar with Chebfun system
 Implement QTTFun 0.1 with basic overloaded functions (arithmetics, integrals, etc.)
TTToolbox production¶
Problem description.¶
TTToolbox (http://github.com/oseledets/ttpy), there is also a MATLAB version, is our basic software for working with tensors, and it is actively used in many groups around the world. However it is not welldocumented and the number of examples is limited. The codebase should be also cleaned as well.
Tasks.¶
 Get familiar with tensor train Toolbox
 Implement basic examples
 Try to document the code, find bugs, propose new functionality
Tensors on GPU¶
Problem description.¶
Tensor train is a very efficient representation of multidimensional tensors. However, there are usecases when not only an asymptotic complexity is needed, but the actual computation speed matters. Our main application in mind is machine learning with lowrank constraints, when someone has to do many iterations, and if it is possible to speedup the computations on GPU, it also improved the results. The TTToolbox (http://github.com/oseledets/ttpy) is implemented in Python with no GPU support. The goal of this project is twofold: get familiar with modern GPU programming techniques, including pyopencl and Loo.py and based upon those, build a GPU version of basic tensor algorithms
Tasks.¶
 Get familiar with tensor train Toolbox
 Get familiar with GPU programming with pyopencl and Loo.py
 Implement a prototype code for basic TT algorithms on GPU, evaluate their performance compared to the peak one
Tensors on MPI¶
Problem description.¶
Tensor train is a very efficient representation of multidimensional tensors. There are usecases, when the representation is so large that is does not fit into the memory (i.e., large TTranks) and parallelization is required. The goal of this project is to try to figure out how the algorithms implemented in the TTToolbox (http://github.com/oseledets/ttpy) can be parallelized (for example, using mpi4py) and test the resulting prototype. Moreover,the actual parametrization of TT is very sequential, and it would be really interesting to consider asyncronous approaches to TT optimization.
Tasks.¶
 Get familiar with tensor train Toolbox
 Get familiar with MPI programming using mpi4py
 Implement a prototype code for basis TTalgorithms using MPI, evaluate their performance
Volume integral equation solvers using QTT¶
Problem description.¶
Probably you have some understanding, what a partial differential equation is. However, there are cases, when volume integral equations (i.e., the system has the form \(K u = f\), and \(K\) is a nonlocal operator, for example,
After discretization, we are left with \(N^3 \times N^3\) dense matrix. For a uniform grid, the complexity is then greatly reduced by using Fast Fourier Transform (FFT) to \(\mathcal{O}(N^3 \log N)\) for one matrixbyvector product. The goal of this project is to reduce this complexity much further, to \(\mathcal{O}(N)\) or even \(\mathcal{O}(\log^{\alpha}(N)\) using quantized tensor train representation.
Tasks.¶
 Get familiar with volume integral equations
 Pick one interesting VIE (probably with some application in mind)
 Get familiar with Tensor Train/ QTT formats
 Implement a basic solver for VIE using TT/QTT formats using TTToolbox
Logistic matrix factorization using Riemannian optimization¶
Problem description.¶
Lowrank matrix factorization of the form
where \(U\) is \(n \times r\) and \(V\) is \(m \times r\), appears in many applications, for example in recommender systems, where the rows enumerate the users, and the columns  the product. However, the typical norm used is the Frobenius norm, and it actually does not fit very well: we are interested only in the prediction of like/dislike, but not the actual numerical value. Thus, the optimization should be formulated in a nonstandard way. Logistic matrix factorization is one of the possible ways to do so. Optimization of nonquadratic functionals can be done using Riemannian optimization in a very efficient way. This is the goal of this project.
Tasks.¶
 Understand where the logistic matrix factorization comes from
 Get familiar with basic Riemannian optimization techniques
 Implement a Riemannian optimization approach for logistic matrix factorization
 Compare with existing software on standard examples.