| 1. |
- Chen, Wei, et al.
(författare)
-
Characterizing the Positive Semidefiniteness of Signed Laplacians via Effective Resistances
- 2016
-
Ingår i: 2016 IEEE 55th Conference on Decision and Control, CDC 2016. - : Institute of Electrical and Electronics Engineers (IEEE). - 9781509018376 ; , s. 985-990
-
Konferensbidrag (refereegranskat)abstract
- A symmetric signed Laplacian matrix uniquely defines a resistive electrical circuit, where the negative weights correspond to negative resistances. The positive semidefiniteness of signed Laplacian matrices is studied in this paper using the concept of effective resistance. We show that a signed Laplacian matrix is positive semidefinite with a simple zero eigenvalue if, and only if, the underlying graph is connected, and a suitably defined effective resistance matrix is positive definite.
|
|
| 2. |
- Chen, Wei, et al.
(författare)
-
On Spectral Properties of Signed Laplacians With Connections to Eventual Positivity
- 2021
-
Ingår i: IEEE Transactions on Automatic Control. - : Institute of Electrical and Electronics Engineers (IEEE). - 0018-9286 .- 1558-2523. ; 66:5, s. 2177-2190
-
Tidskriftsartikel (refereegranskat)abstract
- Signed graphs have appeared in a broad variety of applications, ranging from social networks to biological networks, from distributed control and computation to power systems. In this article, we investigate spectral properties of signed Laplacians for undirected signed graphs. We find conditions on the negative weights under which a signed Laplacian is positive semidefinite via the Kron reduction and multiport network theory. For signed Laplacians that are indefinite, we characterize their inertias with the same framework. Furthermore, we build connections between signed Laplacians, generalized M-matrices, and eventually exponentially positive matrices.
|
|
| 3. |
- Chen, Yongxin, et al.
(författare)
-
An Efficient Algorithm for Matrix-Valued and Vector-Valued Optimal Mass Transport
- 2018
-
Ingår i: Journal of Scientific Computing. - : Springer Science and Business Media LLC. - 0885-7474 .- 1573-7691. ; 77:1, s. 79-100
-
Tidskriftsartikel (refereegranskat)abstract
- We present an efficient algorithm for recent generalizations of optimal mass transport theory to matrix-valued and vector-valued densities. These generalizations lead to several applications including diffusion tensor imaging, color image processing, and multi-modality imaging. The algorithm is based on sequential quadratic programming. By approximating the Hessian of the cost and solving each iteration in an inexact manner, we are able to solve each iteration with relatively low cost while still maintaining a fast convergence rate. The core of the algorithm is solving a weighted Poisson equation, where different efficient preconditioners may be employed. We utilize incomplete Cholesky factorization, which yields an efficient and straightforward solver for our problem. Several illustrative examples are presented for both the matrix and vector-valued cases.
|
|
| 4. |
|
|
| 5. |
- Fan, Jiaojiao, et al.
(författare)
-
On the complexity of the optimal transport problem with graph-structured cost
- 2022
-
Ingår i: Proceedings of The 25th International Conference on Artificial Intelligence and Statistics. - : PMLR. ; , s. 9147-9165
-
Konferensbidrag (refereegranskat)abstract
- Multi-marginal optimal transport (MOT) is a generalization of optimal transport to multiple marginals. Optimal transport has evolved into an important tool in many machine learning applications, and its multi-marginal extension opens up for addressing new challenges in the field of machine learning. However, the usage of MOT has been largely impeded by its computational complexity which scales exponentially in the number of marginals. Fortunately, in many applications, such as barycenter or interpolation problems, the cost function adheres to structures, which has recently been exploited for developing efficient computational methods. In this work we derive computational bounds for these methods. In particular, with $m$ marginal distributions supported on $n$ points, we provide a $ \mathcal\tilde O(d(\mathcalT)m n^w(G)+1ε^-2)$ bound for a ε-accuracy when the problem is associated with a graph that can be factored as a junction tree with diameter $d(\mathcalT)$ and tree-width $w(G)$. For the special case of the Wasserstein barycenter problem, which corresponds to a star-shaped tree, our bound is in alignment with the existing complexity bound for it.
|
|
| 6. |
- Haasler, Isabel, et al.
(författare)
-
Estimating ensemble flows on a hidden Markov chain
- 2019
-
Ingår i: Proceedings of the IEEE Conference on Decision and Control. - : Institute of Electrical and Electronics Engineers Inc.. - 9781728113982 ; , s. 1331-1338
-
Konferensbidrag (refereegranskat)abstract
- We propose a new framework to estimate the evolution of an ensemble of indistinguishable agents on a hidden Markov chain using only aggregate output data. This work can be viewed as an extension of the recent developments in optimal mass transport and Schrödinger bridges to the finite state space hidden Markov chain setting. The flow of the ensemble is estimated by solving a maximum likelihood problem, which has a convex formulation at the infinite-particle limit, and we develop a fast numerical algorithm for it. We illustrate in two numerical examples how this framework can be used to track the flow of identical and indistinguishable dynamical systems.
|
|
| 7. |
- Haasler, Isabel, et al.
(författare)
-
Multi-Marginal Optimal Transport and Probabilistic Graphical Models
- 2021
-
Ingår i: IEEE Transactions on Information Theory. - : IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC. - 0018-9448 .- 1557-9654. ; 67:7, s. 4647-4668
-
Tidskriftsartikel (refereegranskat)abstract
- We study multi-marginal optimal transport problems from a probabilistic graphical model perspective. We point out an elegant connection between the two when the underlying cost for optimal transport allows a graph structure. In particular, an entropy regularized multi-marginal optimal transport is equivalent to a Bayesian marginal inference problem for probabilistic graphical models with the additional requirement that some of the marginal distributions are specified. This relation on the one hand extends the optimal transport as well as the probabilistic graphical model theories, and on the other hand leads to fast algorithms for multi-marginal optimal transport by leveraging the well-developed algorithms in Bayesian inference. Several numerical examples are provided to highlight the results.
|
|
| 8. |
- Haasler, Isabel, et al.
(författare)
-
Multimarginal optimal transport with a tree-structured cost and the schrödinger bridge problem
- 2021
-
Ingår i: SIAM Journal of Control and Optimization. - : Society for Industrial & Applied Mathematics (SIAM). - 0363-0129 .- 1095-7138. ; 59:4, s. 2428-2453
-
Tidskriftsartikel (refereegranskat)abstract
- The optimal transport problem has recently developed into a powerful framework for various applications in estimation and control. Many of the recent advances in the theory and application of optimal transport are based on regularizing the problem with an entropy term, which connects it to the Schrodinger bridge problem and thus to stochastic optimal control. Moreover, the entropy regularization makes the otherwise computationally demanding optimal transport problem feasible even for large scale settings. This has led to an accelerated development of optimal transport based methods in a broad range of fields. Many of these applications have an underlying graph structure, for instance, information fusion and tracking problems can be described by trees. In this work we consider multimarginal optimal transport problems with a cost function that decouples according to a tree structure. The entropy regularized multimarginal optimal transport problem can be viewed as a generalization of the Schrodinger bridge problem with the same tree-structure, and by utilizing these connections we extend the computational methods for the classical optimal transport problem in order to solve structured multimarginal optimal transport problems in an efficient manner. In particular, the algorithm requires only matrix-vector multiplications of relatively small dimensions. We show that the multimarginal regularization introduces less diffusion, compared to the commonly used pairwise regularization, and is therefore more suitable for many applications. Numerical examples illustrate this, and we finally apply the proposed framework for the tracking of an ensemble of indistinguishable agents.
|
|
| 9. |
|
|
| 10. |
- Haasler, Isabel, et al.
(författare)
-
Scalable Computation of Dynamic Flow Problems via Multimarginal Graph-Structured Optimal Transport
- 2024
-
Ingår i: Mathematics of Operations Research. - 0364-765X .- 1526-5471. ; 49:2, s. 986-1011
-
Tidskriftsartikel (refereegranskat)abstract
- In this work, we develop a new framework for dynamic network flow pro-blems based on optimal transport theory. We show that the dynamic multicommodity minimum-cost network flow problem can be formulated as a multimarginal optimal transport problem, where the cost function and the constraints on the marginals are asso-ciated with a graph structure. By exploiting these structures and building on recent advances in optimal transport theory, we develop an efficient method for such entropy -regularized optimal transport problems. In particular, the graph structure is utilized to efficiently compute the projections needed in the corresponding Sinkhorn iterations, and we arrive at a scheme that is both highly computationally efficient and easy to implement. To illustrate the performance of our algorithm, we compare it with a state-of-the-art linear programming (LP) solver. We achieve good approximations to the solution at least one order of magnitude faster than the LP solver. Finally, we showcase the methodology on a traffic routing problem with a large number of commodities.
|
|
