22 citations · 63 across the 20 of their papers we have counts for
23 papers
Quiver Semistability and Structured Kalman Decompositions for Networked Linear Dynamical Systems
Kazuo Murota, Tasuku Soma
We introduce new notions of controllability and observability for networked linear time-invariant (LTI) systems based on -semistability of quiver representations. Utilizing King…
Numerically stable variants of overrelaxation for operator Sinkhorn iteration
Henrik Eisenmann, Tasuku Soma, Xun Tang +1
We consider accelerated versions of the operator Sinkhorn iteration (OSI) for solving scaling problems for completely positive maps. Based on the interpretation of OSI as alternati…
-Approximation Algorithms for Bipartiteness Ratio
Tasuku Soma, Mingquan Ye, Yuichi Yoshida
We propose an -approximation algorithm for the bipartiteness ratio of undirected graphs introduced by Trevisan (SIAM Journal on Computing, vol. 41, no. 6, 2012), where $…
Accelerating operator Sinkhorn iteration with overrelaxation
Tasuku Soma, André Uschmajew
We propose accelerated versions of the operator Sinkhorn iteration for operator scaling using successive overrelaxation. We analyze the local convergence rates of these accelerated…
Algorithmic aspects of semistability of quiver representations
Yuni Iwamasa, Taihei Oki, Tasuku Soma
We study the semistability of quiver representations from an algorithmic perspective. We present efficient algorithms for several fundamental computational problems on the semistab…
Online Algorithms for Spectral Hypergraph Sparsification
Tasuku Soma, Kam Chuen Tung, Yuichi Yoshida
We provide the first online algorithm for spectral hypergraph sparsification. In the online setting, hyperedges with positive weights are arriving in a stream, and upon the arrival…
Algebraic combinatorial optimization on the degree of determinants of noncommutative symbolic matrices
Hiroshi Hirai, Yuni Iwamasa, Taihei Oki +1
We address the computation of the degrees of minors of a noncommutative symbolic matrix of form \[ A[c] := \sum_{k=1}^m A_k t^{c_k} x_k, \] where are matrices over a field $\…
Near-Optimal Algorithms for Group Distributionally Robust Optimization and Beyond
Tasuku Soma, Khashayar Gatmiry, Sharut Gupta +1
Distributionally robust optimization (DRO) can improve the robustness and fairness of learning methods. In this paper, we devise stochastic algorithms for a class of DRO problems i…
Shrunk subspaces via operator Sinkhorn iteration
Cole Franks, Tasuku Soma, Michel X. Goemans
A recent breakthrough in Edmonds' problem showed that the noncommutative rank can be computed in deterministic polynomial time, and various algorithms for it were devised. However,…
Algebraic Algorithms for Fractional Linear Matroid Parity via Non-commutative Rank
Taihei Oki, Tasuku Soma
Matrix representations are a powerful tool for designing efficient algorithms for combinatorial optimization problems such as matching, and linear matroid intersection and parity.…
Online Risk-Averse Submodular Maximization
Tasuku Soma, Yuichi Yoshida
We present a polynomial-time online algorithm for maximizing the conditional value at risk (CVaR) of a monotone stochastic submodular function. Given i.i.d. samples from an und…
Information geometry of operator scaling
Takeru Matsuda, Tasuku Soma
Matrix scaling is a classical problem with a wide range of applications. It is known that the Sinkhorn algorithm for matrix scaling is interpreted as alternating e-projections from…
Statistical Learning with Conditional Value at Risk
Tasuku Soma, Yuichi Yoshida
We propose a risk-averse statistical learning framework wherein the performance of a learning algorithm is evaluated by the conditional value-at-risk (CVaR) of losses rather than t…
Fast greedy algorithms for dictionary selection with generalized sparsity constraints
Kaito Fujii, Tasuku Soma
In dictionary selection, several atoms are selected from finite candidates that successfully approximate given data points in the sparse representation. We propose a novel efficien…
Spectral Sparsification of Hypergraphs
Tasuku Soma, Yuichi Yoshida
For an undirected/directed hypergraph , its Laplacian is defined such that its ``quadratic form'' $\boldsymbol{x}^\top L_G(\boldsym…
No-regret algorithms for online -submodular maximization
Tasuku Soma
We present a polynomial time algorithm for online maximization of -submodular maximization. For online (nonmonotone) -submodular maximization, our algorithm achieves a tight…
Maximally Invariant Data Perturbation as Explanation
Satoshi Hara, Kouichi Ikeno, Tasuku Soma +1
While several feature scoring methods are proposed to explain the output of complex machine learning models, most of them lack formal mathematical definitions. In this study, we pr…
Polynomial-Time Algorithms for Submodular Laplacian Systems
Kaito Fujii, Tasuku Soma, Yuichi Yoshida
Let be an undirected graph, be the associated Laplacian matrix, and be a vector. Solving the Laplacian system $L_G x…
A New Approximation Guarantee for Monotone Submodular Function Maximization via Discrete Convexity
Tasuku Soma, Yuichi Yoshida
In monotone submodular function maximization, approximation guarantees based on the curvature of the objective function have been extensively studied in the literature. However, th…
On orthogonal tensors and best rank-one approximation ratio
Zhening Li, Yuji Nakatsukasa, Tasuku Soma +1
As is well known, the smallest possible ratio between the spectral norm and the Frobenius norm of an matrix with is and is (up to scalar scaling…
Non-monotone DR-Submodular Function Maximization
Tasuku Soma, Yuichi Yoshida
We consider non-monotone DR-submodular function maximization, where DR-submodularity (diminishing return submodularity) is an extension of submodularity for functions over the inte…
Finding a low-rank basis in a matrix subspace
Yuji Nakatsukasa, Tasuku Soma, André Uschmajew
For a given matrix subspace, how can we find a basis that consists of low-rank matrices? This is a generalization of the sparse vector problem. It turns out that when the subspace…
Maximizing Monotone Submodular Functions over the Integer Lattice
Tasuku Soma, Yuichi Yoshida
The problem of maximizing non-negative monotone submodular functions under a certain constraint has been intensively studied in the last decade. In this paper, we address the probl…