skip to main content
Idioma:
Primo Search
Clear Search Box
Search in: Busca Geral
Busca Avançada
Busca por Índices
Tipo de recurso Mostra resultados com: Mostra resultados com: Índice

Performance of Group Testing Algorithms With Near-Constant Tests Per Item

Johnson, Oliver ; Aldridge, Matthew ; Scarlett, Jonathan

IEEE transactions on information theory, 2019-02, Vol.65 (2), p.707-723 [Periódico revisado por pares]

New York: IEEE

Texto completo disponível

Citações Citado por
  • Título:
    Performance of Group Testing Algorithms With Near-Constant Tests Per Item
  • Autor: Johnson, Oliver ; Aldridge, Matthew ; Scarlett, Jonathan
  • Assuntos: Algorithm design and analysis ; Algorithms ; Combinatorial analysis ; Computer simulation ; Decoding ; Design defects ; Group dynamics ; group testing ; Matching pursuit algorithms ; measurement design ; Optimization ; performance bounds ; sparse models ; Time-frequency analysis
  • É parte de: IEEE transactions on information theory, 2019-02, Vol.65 (2), p.707-723
  • Descrição: We consider the nonadaptive group testing with N items, of which K = Θ(N θ ) are defective. We study a test design in which each item appears in nearly the same number of tests. For each item, we independently pick L tests uniformly at random with replacement and place the item in those tests. We analyze the performance of these designs with simple and practical decoding algorithms in a range of sparsity regimes and show that the performance is consistently improved in comparison with standard Bernoulli designs. We show that our new design requires roughly 23% fewer tests than a Bernoulli design when paired with the simple decoding algorithms known as combinatorial orthogonal matching pursuit and definite defectives (DD). This gives the best known nonadaptive group testing performance for θ > 0.43 and the best proven performance with a practical decoding algorithm for all θ ∈ (0, 1). We also give a converse result showing that the DD algorithm is optimal with respect to our randomized design when θ > 1/2. We complement our theoretical results with simulations that show a notable improvement over Bernoulli designs in both sparse and dense regimes.
  • Editor: New York: IEEE
  • Idioma: Inglês
Voltar para lista de resultados

  • Realização: ABCD-USP USP   Logos de Redes Sociais: Freepik

Buscando em bases de dados remotas. Favor aguardar.