Consider a directed, rooted graph G = (V ∪ {r}, E) where each vertex in V has a partial order preference over its incoming edges. The preferences of a vertex naturally extend to preferences over arborescences rooted ...
详细信息
We present some characterizations of the ordered weighted l(1) norm (aka sorted l(1) norm) and of the vector Ky-Fan norm as solutions to linear programs involving reasonably many variables and constraints. Such linear...
详细信息
We present some characterizations of the ordered weighted l(1) norm (aka sorted l(1) norm) and of the vector Ky-Fan norm as solutions to linear programs involving reasonably many variables and constraints. Such linear characterizations can be exploited to recast and effortlessly solve a variety of convex optimization problems involving these norms. Similar linear characterizations are given for the dual norms of the ordered weighted l(1) norm and the Ky-Fan norm.
A min-max theorem is developed for the multiway cut problem of edge-weighted trees. We present a polynomial time algorithm to construct an optimal dual solution, if edge weights come in unary representation. Applicati...
详细信息
A min-max theorem is developed for the multiway cut problem of edge-weighted trees. We present a polynomial time algorithm to construct an optimal dual solution, if edge weights come in unary representation. Applications to biology also require some more complex edge weights. We describe a dynamic programming type algorithm for this more general problem from biology and show that our min-max theorem does not apply to it.
This paper considers the problem of clustering a collection of unlabeled data points assumed to lie near a union of lower-dimensional planes. As is common in computer vision or unsupervised learning applications, we d...
详细信息
This paper considers the problem of clustering a collection of unlabeled data points assumed to lie near a union of lower-dimensional planes. As is common in computer vision or unsupervised learning applications, we do not know in advance how many subspaces there are nor do we have any information about their dimensions. We develop a novel geometric analysis of an algorithm named sparse subspace clustering (SSC) [In IEEE Conference on Computer Vision and Pattern Recognition, 2009. CVPR 2009 (2009) 2790-2797. IEEE], which significantly broadens the range of problems where it is provably effective. For instance, we show that SSC can recover multiple subspaces, each of dimension comparable to the ambient dimension. We also prove that SSC can correctly cluster data points even when the subspaces of interest intersect. Further, we develop an extension of SSC that succeeds when the data set is corrupted with possibly overwhelmingly many outliers. Underlying our analysis are clear geometric insights, which may bear on other sparse recovery problems. A numerical study complements our theoretical analysis and demonstrates the effectiveness of these methods.
暂无评论