Multimedia data embedding, such as video, image or audio data watermarking. In one embodiment, a computer-implemented method first receives a vector x of N data samples, where X=[x(0)x(1) . . . x(N−1)] and represents multimedia. Next, the method receives a vector p, where P=[p(0)p(1) . . . p(N−1)] and represents a pseudo-random sequence. Finally, the method generates a new vector x′ in which the vector p is embedded in the vector x, such that x′=[x′(0)x′(1) . . . x′(N−1)] and x′=x+aq, where a comprises a perception-based scaling factor and the vector q comprises a perceptually weighted pseudo-random sequence based on the vector p.