We give robust recovery results for synchronization on the rotation group, Formula omitted. In particular, we consider an adversarial corruption setting, where a limited percentage of the ...observations are arbitrarily corrupted. We develop a novel algorithm that exploits Tukey depth in the tangent space of Formula omitted. This algorithm, called Depth Descent Synchronization, exactly recovers the underlying rotations up to an outlier percentage of Formula omitted, which corresponds to 1/4 for Formula omitted and 1/8 for Formula omitted. In the case of Formula omitted, we demonstrate that a variant of this algorithm converges linearly to the ground truth rotations. We implement this algorithm for the case of Formula omitted and demonstrate that it performs competitively on baseline synthetic data.
Predictive Algorithms for a Crisis Sotillo, Claudia L; Franco, Idalid; Arriaga, Alexander F
Critical care medicine,
07/2022, Letnik:
50, Številka:
7
Journal Article
In this paper, we consider the problem of computing the rank of a block-structured symbolic matrix (a generic partitioned matrix) Formula omitted, where Formula omitted is a Formula omitted matrix ...over a field Formula omitted and Formula omitted is an indeterminate for Formula omitted and Formula omitted. This problem can be viewed as an algebraic generalization of the bipartite matching problem and was considered by Iwata and Murota (SIAM J Matrix Anal Appl 16(3):719-734, 1995). Recent interests in this problem lie in the connection with non-commutative Edmonds' problem by Ivanyos et al. (Comput Complex 27:561-593, 2018) and Garg et al. (Found. Comput. Math. 20:223-290, 2020), where a result by Iwata and Murota implicitly states that the rank and non-commutative rank (nc-rank) are the same for this class of symbolic matrices. The main result of this paper is a simple and combinatorial Formula omitted-time algorithm for computing the symbolic rank of a Formula omitted-type generic partitioned matrix of size Formula omitted. Our algorithm is inspired by the Wong sequence algorithm by Ivanyos et al. for the nc-rank of a general symbolic matrix, and requires no blow-up operation, no field extension, and no additional care for bounding the bit-size. Moreover it naturally provides a maximum rank completion of A for an arbitrary field Formula omitted.
We consider the restricted inverse optimal value problem on shortest path under weighted Formula omitted norm on trees (RIOVSPT Formula omitted). It aims at adjusting some edge weights to minimize ...the total cost under weighted Formula omitted norm on the premise that the length of the shortest root-leaf path of the tree is lower-bounded by a given value D, which is just the restriction on the length of a given root-leaf path Formula omitted. If we ignore the restriction on the path Formula omitted, then we obtain the minimum cost shortest path interdiction problem on trees (MCSPIT Formula omitted). We analyze some properties of the problem (RIOVSPT Formula omitted) and explore the relationship of the optimal solutions between (MCSPIT Formula omitted) and (RIOVSPT Formula omitted). We first take the optimal solution of the problem (MCSPIT Formula omitted) as an initial infeasible solution of problem (RIOVSPT Formula omitted). Then we consider a slack problem Formula omitted, where the length of the path Formula omitted is greater than D. We obtain its feasible solutions gradually approaching to an optimal solution of the problem (RIOVSPT Formula omitted) by solving a series of subproblems Formula omitted. It aims at determining the only weight-decreasing edge on the path Formula omitted with the minimum cost so that the length of the shortest root-leaf path is no less than D. The subproblem can be solved by searching for a minimum cost cut in O(n) time. The iterations continue until the length of the path Formula omitted equals D. Consequently, the time complexity of the algorithm is Formula omitted and we present some numerical experiments to show the efficiency of the algorithm. Additionally, we devise a linear time algorithm for the problem (RIOVSPT Formula omitted) under unit Formula omitted norm.
In view of some shortcomings of traditional vertex 1-center (V1C), we introduce a vertex quickest 1-center (VQ1C) problem on a tree, which aims to find a vertex such that the maximum transmission ...time to transmit Formula omitted units data is minimum. We first characterize some intrinsic properties of VQ1C and design a binary search algorithm in Formula omitted time based on the relationship between V1C and VQ1C, where n is the number of vertices. Furthermore, we investigate the inverse VQ1C problem under weighted Formula omitted norm, in which we modify a given capacity vector in an optimal way such that a prespecified vertex becomes the vertex quickest 1-center. We introduce a concept of an effective modification and provide some optimality conditions for the problem. Then we propose an Formula omitted time algorithm. Finally, we show some numerical experiments to verify the efficiency of the algorithms.
The max+sum spanning tree (MSST) problem is to determine a spanning tree T whose combined weight Formula omitted is minimum for a given edge-weighted undirected network G(V, E, c, w). This problem ...can be solved within Formula omitted time, where m and n are the numbers of edges and nodes, respectively. An inverse MSST problem (IMSST) aims to determine a new weight vector Formula omitted so that a given Formula omitted becomes an optimal MSST of the new network Formula omitted. The IMSST problem under weighted Formula omitted norm is to minimize the modification cost Formula omitted, where q(e) is a cost modifying the weight w(e). We first provide some optimality conditions of the problem. Then we propose a strongly polynomial time algorithm in Formula omitted time based on a binary search and a greedy method. There are O(m) iterations and we solve an MSST problem under a new weight in each iteration. Finally, we perform some numerical experiments to show the efficiency of the algorithm.
Maximum a posteriori (MAP) inference is an important task for graphical models. Due to complex dependencies among variables in realistic models, finding an exact solution for MAP inference is often ...intractable. Thus, many approximation methods have been developed, among which the linear programming (LP) relaxation based methods show promising performance. However, one major drawback of LP relaxation is that it is possible to give fractional solutions. Instead of presenting a tighter relaxation, in this work we propose a continuous but equivalent reformulation of the original MAP inference problem, called LS-LP. We add the Formula omitted-sphere constraint onto the original LP relaxation, leading to an intersected space with the local marginal polytope that is equivalent to the space of all valid integer label configurations. Thus, LS-LP is equivalent to the original MAP inference problem. We propose a perturbed alternating direction method of multipliers (ADMM) algorithm to optimize the LS-LP problem, by adding a sufficiently small perturbation Formula omitted onto the objective function and constraints. We prove that the perturbed ADMM algorithm globally converges to the Formula omitted-Karush-Kuhn-Tucker ( Formula omitted-KKT) point of the LS-LP problem. The convergence rate will also be analyzed. Experiments on several benchmark datasets from Probabilistic Inference Challenge (PIC 2011) and OpenGM 2 show competitive performance of our proposed method against state-of-the-art MAP inference methods.
PDF
