Reconstrucción de trazas de matrices y hipermatrices

Una traza de una secuencia se genera al eliminar cada bit de la secuencia de forma independiente con una probabilidad fija. El problema de reconstrucción de trazas, bien estudiado, pregunta cuántas trazas son necesarias para reconstruir una secuencia binaria desconocida con alta probabilidad. En este documento, estudiamos la versión multivariada de este problema para matrices y hipermatrices, donde una traza se genera al eliminar cada fila/columna de la matriz o cada sección de la hipermatriz independientemente con una probabilidad constante. Anteriormente, Krishnamurthy et al. demostraron que (O (n^d/ (d+2) ) ) trazas son suficientes para reconstruir cualquier matriz n n desconocida (para d=2) y cualquier hipermatriz n^ d desconocida. Al desarrollar un procedimiento de reducción de dimensiones y establecer una versión multivariada del resultado tipo Littlewood, mejoramos este límite superior al mostrar que (O (n^3/7) ) trazas son suficientes para reconstruir cualquier matriz n n desconocida, y (O (n^3/5) ) trazas son suficientes para reconstruir cualquier hipermatriz n^ d desconocida. Esto rompe la tendencia trivial de (O (n) ) a medida que la dimensión d crece.