A structured watermark may be embedded in data by applying an irregular mapping of variations defined by the structured watermark to frequency domain values representing the data. In particular, the frequency domain representation of the data comprises an ordered set of frequency domain values. The structured watermark is used to define an ordered set of variations to be applied to the frequency domain values. Each variation is a value defined by the structured watermark. An irregular mapping from positions in the ordered set of variations to positions in the ordered set of frequency domain values is defined. This irregular mapping is one-to-one and invertible. Application of the irregular mapping to the set of variations results in a set of values that may appear to be noise both in the frequency domain and in the signal domain of the data. The signal domain of the data may be n-dimensional, and may be a spatial, temporal or other domain from which data may be converted to the frequency domain. The signal domain of the data may be continuous or discrete. Each frequency domain value is modified by the variation mapped to the position of the frequency domain value by the irregular mapping. A frequency domain value may be modified using an additive or multiplicative operation. Using additive embedding, the modifications to the frequency domain values may be effected in the signal domain without computing the frequency domain values of the data by transforming, to the signal domain, the results of applying the irregular mapping to the set of variations. The watermark may be detected in target data by using the inverse of the irregular mapping on the frequency domain representation of the target data. Because the watermark is structured, it may be perceptible in the target data after the target data is processed by the inverse of the irregular mapping. A similarity metric, such as correlation, also can be used to detect the presence of the structured watermark in the processed target data.