Base mínima para el conjunto de vectores binarios usando XOR

Me sorprendería si este no es un problema bien estudiado, pero no estoy seguro de qué más buscar en este momento: se le da un conjunto de -vectores binarios . El problema es encontrar otro conjunto de -vectores binarios , con un tamaño mínimo, de modo que cada vector en puede expresarse por los resultados XOR de algún subconjunto de (por lo que es esencialmente una base para usando XOR en lugar de la suma y permitiendo solo coeficientes binarios en la combinación lineal).$n$$S \subset \{0,1\}^n$$n$$B \subset \{0,1\}^n$$|B|$$S$$B$$B$$S$

En cierto modo, esta es una forma de PCA para vectores binarios. Mientras buscaba literatura sobre este problema, me encontré con el problema de base discreta también discutido en esta tesis doctoral , que parece estar estrechamente relacionado. En lugar de XOR usa OR, y aquíes una entrada adicional (y la tarea es minimizar el error al representar con vectores de ). Este problema es NP-hard. ¿Se aplica lo mismo al problema que he presentado anteriormente, o hay una solución eficiente? Cualquier sugerencia a la literatura existente sería muy apreciada.$|B|$$S$$B$

Si trata a sus vectores como sobre el campo lugar de sobre el conjunto , entonces lo que pide es encontrar una base para la extensión de un conjunto de vectores. Este es un problema bien estudiado en álgebra lineal, para el cual probablemente conoces la solución. (Una opción es la eliminación gaussiana).$GF(2)$$\{0,1\}$