Is there any way to represent the Euclidean norm with random basis?
Yes, absolutely: compose the norm with a map from the given basis to the standard basis. If the basis is given as the columns of a matrix A, then the expression for the square of the norm is |A^-1 x|^2 = x^T A^-T A^-1 x.
Thanks for the answer
Does the definition of Euclidean inner product holds for Hamming space? My intuition is that it should since Hamming space can be viewed as a subspace of Euclidean space.
@anonymous_panda The whole point of a Hamming space is that it uses a very particular notion of distance; the Hamming distance. It's not clear the Euclidean inner product provides much value in this setting.