چكيده به لاتين
The local isomorphism of a manifold with Euclidean space helps to generalize and solve the inverse problems of Euclidean space to the manifold space. Although data structures are usually in the form of manifolds, they are generally modeled on Euclidean space for simplicity, which can result in higher computational complexity and lower accuracy. In general, inverse modeling and problem solving is done using the definition of an optimization problem and its solution. In this dissertation, in terms of side information about inverse problems, we present the geometric structure for each inverse problem that is used to solve the optimization problem. The inverse problems discussed in this dissertation are:
-High rank matrix completion
The first inverse problem is the problem of high rank matrix completion that has various applications, including identifying the Internet network topology. We solve this problem by having additional information about row and column space and presenting an optimization problem on a new manifold. The performance improvement of the proposed algorithm in term of the normalized error criterion is in some cases more than 15% compared to other existing methods. As the probability of observation increases, the error recovery performance of our proposed algorithm is greatly improved until the error value reaches about 0.12. While the performance of the best other algorithms is about 0.19.
- Completion of low-rank bipolar matrices;
The second inverse problem is the problem of completing low-rank bipolar matrices, one of the applications of which is collaborative filtering. In order to solve these inverse problems, we consider two different modes of low observation error and high observation error, for both cases, we propose manifold optimization problems and prove the convergence of some algorithm for them. In the first case, we use the manifold of rank-one matrices and also use the gradient descent algorithm to solve the problem. In the second case, we model the problem on a Riemannian sphere and use the trust region method to solve the problem. For both cases, we have considered the specific application of haplotype assembly. The simulation results in the first case show an improvement in the performance of haplotype estimates of about 10% by the Hamming distance criterion compared to other algorithms. In the second case, in some experiments, performance improvement compared to other algorithms is observed up to 20% by Hamming distance criterion.
- Solve the maximum cut problem;
The third inverse problem is the problem of maximum cut of an unweighted undirected graph without loop, which is used in problems such as data clustering. To solve this problem, we present an optimization problem on the manifold that contains the properties of the maximum cut problem and prove its convergence. According to the simulation results, our proposed algorithm is 35 times faster than other algorithms in solving problems for known graphs with a maximum number of vertices 3000; While it can reach the cut size of 0.96 with the best algorithms available. More importantly, our proposed algorithm is easily capable of solving the problem of maximum cut for very large vertices. While other existing algorithms, even for 5000 vertices, it takes a very long time (more than 10,000 seconds) to converge. Therefore, the proposed algorithm is a very fast and accurate algorithm in solving the maximum cut problem.
