3 Search Results for "Zhou, Tianyi"

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2023.88
Space-Efficient Interior Point Method, with Applications to Linear Programming and Maximum Weight Bipartite Matching

Authors: S. Cliff Liu, Zhao Song, Hengjie Zhang, Lichen Zhang, and Tianyi Zhou

Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)

Abstract
We study the problem of solving linear program in the streaming model. Given a constraint matrix A ∈ ℝ^{m×n} and vectors b ∈ ℝ^m, c ∈ ℝ^n, we develop a space-efficient interior point method that optimizes solely on the dual program. To this end, we obtain efficient algorithms for various different problems: - For general linear programs, we can solve them in Õ(√n log(1/ε)) passes and Õ(n²) space for an ε-approximate solution. To the best of our knowledge, this is the most efficient LP solver in streaming with no polynomial dependence on m for both space and passes. - For bipartite graphs, we can solve the minimum vertex cover and maximum weight matching problem in Õ(√m) passes and Õ(n) space. In addition to our space-efficient IPM, we also give algorithms for solving SDD systems and isolation lemma in Õ(n) spaces, which are the cornerstones for our graph results.
Cite as

S. Cliff Liu, Zhao Song, Hengjie Zhang, Lichen Zhang, and Tianyi Zhou. Space-Efficient Interior Point Method, with Applications to Linear Programming and Maximum Weight Bipartite Matching. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 88:1-88:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{liu_et_al:LIPIcs.ICALP.2023.88,
  author =	{Liu, S. Cliff and Song, Zhao and Zhang, Hengjie and Zhang, Lichen and Zhou, Tianyi},
  title =	{{Space-Efficient Interior Point Method, with Applications to Linear Programming and Maximum Weight Bipartite Matching}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{88:1--88:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-278-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{261},
  editor =	{Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.88},
  URN =		{urn:nbn:de:0030-drops-181408},
  doi =		{10.4230/LIPIcs.ICALP.2023.88},
  annote =	{Keywords: Convex optimization, interior point method, streaming algorithm}
}
Document
DOI: 10.4230/LITES.8.1.1
Susceptibility to Image Resolution in Face Recognition and Training Strategies to Enhance Robustness

Authors: Martin Knoche, Stefan Hörmann, and Gerhard Rigoll

Published in: LITES, Volume 8, Issue 1 (2022): Special Issue on Embedded Systems for Computer Vision. Leibniz Transactions on Embedded Systems, Volume 8, Issue 1

Abstract
Many face recognition approaches expect the input images to have similar image resolution. However, in real-world applications, the image resolution varies due to different image capture mechanisms or sources, affecting the performance of face recognition systems. This work first analyzes the image resolution susceptibility of modern face recognition. Face verification on the very popular LFW dataset drops from 99.23% accuracy to almost 55% when image dimensions of both images are reduced to arguable very poor resolution. With cross-resolution image pairs (one HR and one LR image), face verification accuracy is even worse. This characteristic is investigated more in-depth by analyzing the feature distances utilized for face verification. To increase the robustness, we propose two training strategies applied to a state-of-the-art face recognition model: 1) Training with 50% low resolution images within each batch and 2) using the cosine distance loss between high and low resolution features in a siamese network structure. Both methods significantly boost face verification accuracy for matching training and testing image resolutions. Training a network with different resolutions simultaneously instead of adding only one specific low resolution showed improvements across all resolutions and made a single model applicable to unknown resolutions. However, models trained for one particular low resolution perform better when using the exact resolution for testing. We improve the face verification accuracy from 96.86% to 97.72% on the popular LFW database with uniformly distributed image dimensions between 112 × 112 px and 5 × 5 px. Our approaches improve face verification accuracy even more from 77.56% to 87.17% for distributions focusing on lower images resolutions. Lastly, we propose specific image dimension sets focusing on high, mid, and low resolution for five well-known datasets to benchmark face verification accuracy in cross-resolution scenarios.
Cite as

Martin Knoche, Stefan Hörmann, and Gerhard Rigoll. Susceptibility to Image Resolution in Face Recognition and Training Strategies to Enhance Robustness. In LITES, Volume 8, Issue 1 (2022): Special Issue on Embedded Systems for Computer Vision. Leibniz Transactions on Embedded Systems, Volume 8, Issue 1, pp. 01:1-01:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@Article{knoche_et_al:LITES.8.1.1,
  author =	{Knoche, Martin and H\"{o}rmann, Stefan and Rigoll, Gerhard},
  title =	{{Susceptibility to Image Resolution in Face Recognition and Training Strategies to Enhance Robustness}},
  booktitle =	{LITES, Volume 8, Issue 1 (2022): Special Issue on Embedded Systems for Computer Vision},
  pages =	{01:1--01:20},
  journal =	{Leibniz Transactions on Embedded Systems},
  ISSN =	{2199-2002},
  year =	{2022},
  volume =	{8},
  number =	{1},
  editor =	{Knoche, Martin and H\"{o}rmann, Stefan and Rigoll, Gerhard},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LITES.8.1.1},
  doi =		{10.4230/LITES.8.1.1},
  annote =	{Keywords: recognition, resolution, cross, face, identification}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2021.76
Constructing a Distance Sensitivity Oracle in O(n^2.5794 M) Time

Authors: Yong Gu and Hanlin Ren

Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)

Abstract
We continue the study of distance sensitivity oracles (DSOs). Given a directed graph G with n vertices and edge weights in {1, 2, … , M}, we want to build a data structure such that given any source vertex u, any target vertex v, and any failure f (which is either a vertex or an edge), it outputs the length of the shortest path from u to v not going through f. Our main result is a DSO with preprocessing time O(n^2.5794 M) and constant query time. Previously, the best preprocessing time of DSOs for directed graphs is O(n^2.7233 M), and even in the easier case of undirected graphs, the best preprocessing time is O(n^2.6865 M) [Ren, ESA 2020]. One drawback of our DSOs, though, is that it only supports distance queries but not path queries. Our main technical ingredient is an algorithm that computes the inverse of a degree-d polynomial matrix (i.e. a matrix whose entries are degree-d univariate polynomials) modulo x^r. The algorithm is adapted from [Zhou, Labahn and Storjohann, Journal of Complexity, 2015], and we replace some of its intermediate steps with faster rectangular matrix multiplication algorithms. We also show how to compute unique shortest paths in a directed graph with edge weights in {1, 2, … , M}, in O(n^2.5286 M) time. This algorithm is crucial in the preprocessing algorithm of our DSO. Our solution improves the O(n^2.6865 M) time bound in [Ren, ESA 2020], and matches the current best time bound for computing all-pairs shortest paths.
Cite as

Yong Gu and Hanlin Ren. Constructing a Distance Sensitivity Oracle in O(n^2.5794 M) Time. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 76:1-76:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{gu_et_al:LIPIcs.ICALP.2021.76,
  author =	{Gu, Yong and Ren, Hanlin},
  title =	{{Constructing a Distance Sensitivity Oracle in O(n^2.5794 M) Time}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{76:1--76:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.76},
  URN =		{urn:nbn:de:0030-drops-141450},
  doi =		{10.4230/LIPIcs.ICALP.2021.76},
  annote =	{Keywords: graph theory, shortest paths, distance sensitivity oracles}
}
  • Refine by Author
  • 1 Gu, Yong
  • 1 Hörmann, Stefan
  • 1 Knoche, Martin
  • 1 Liu, S. Cliff
  • 1 Ren, Hanlin
  • Show More...

  • Refine by Classification
  • 1 Computing methodologies → Neural networks
  • 1 Theory of computation → Design and analysis of algorithms
  • 1 Theory of computation → Linear programming
  • 1 Theory of computation → Shortest paths
  • 1 Theory of computation → Streaming, sublinear and near linear time algorithms

  • Refine by Keyword
  • 1 Convex optimization
  • 1 cross
  • 1 distance sensitivity oracles
  • 1 face
  • 1 graph theory
  • Show More...

  • Refine by Type
  • 3 document

  • Refine by Publication Year
  • 1 2021
  • 1 2022
  • 1 2023

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023 Schloss Dagstuhl - LZI GmbH Imprint Privacy Contact