Instead of demanding orthogonal representations, just have them obey the restricted isometry property.
Basically, instead of requiring ∀i≠j:<xi,xj>=0, we just require ∀i≠j:xi⋅xj≤ϵ .
This would allow a polynomial number of sparse shards while still allowing full recovery.
Instead of demanding orthogonal representations, just have them obey the restricted isometry property.
Basically, instead of requiring ∀i≠j:<xi,xj>=0, we just require ∀i≠j:xi⋅xj≤ϵ .
This would allow a polynomial number of sparse shards while still allowing full recovery.