intvert.invert_2D

invert_2D(signal, known_coeffs={}, **lattice_params)

Invert an integer matrix from limited DFT spectrum.

Invert the last two axes of an integer signal from a limited set of sampled DFT coefficients. The sampled frequencies may be provided in known_coeffs, which should be structured like the output of select_coeffs_2D. The input signal should be given in real space, so the known DFT coefficients are obtained by calling mp_dft2 on signal. If no known frequencies are provided, they are chosen automatically from signal by assuming nonzero DFT coefficients are known. It is assumed that a sufficient set of coefficients are known to guarantee uniqueness of inversion.

Parameters:

  • signal (mpfr arraylike) – Sampled 2D signal.

  • known_coeffs (dict, optional) – Dictionary of known frequencies, by default {}

Returns:

Inverted signal.

Return type:

int ndarray

Raises:

InversionError – If inversion fails for any subproblem. The current lattice parameter values are given, so they may be tuned to allow inversion.

See also

sample_2D

constructing the sampled input

select_coeffs_2D

selecting a partial set of known DFT coefficients

invert_1D

analogous 1D function

Parameters:

  • beta0 (float) – Penalty for coefficient of last lattice basis column, by default 1e-1

  • beta1 (float) – Penalty for missing linear constraints with integer coefficients, by default 1e3

  • beta2 (float) – Penalty for missing linear constraints with real coefficients, by default 1e14

  • beta3 (float) – Rescale before truncation, by default 1e2

  • delta (float) – LLL approximation parameter delta, by default 0.9972

  • epsilon (float) – Absolute tolerance for verifying shortest vectors against DFT coefficient data.

Notes

Let \((N_1, N_2)\) be the shape of the last two axes of signal. This dynamic programming implementation of 2D inversion iterates through pairs of divisors of \(N_1, N_2\), with several 1D inversions occuring at each iteration. For details on 1D inversion and the keyword parameters **lattice_params, see invert_1D.

Examples

Sampling and inverting with automatically selected coefficients:

>>> signal = np.arange(10).reshape((2, 5))
>>> sampled = intvert.sample_2D(signal)
>>> np.allclose(intvert.invert_2D(sampled), signal)
True

Sampling and inverting with user-selected coefficients:

>>> known_coeffs = {(2, 5): {frozenset({(0, 0)})}, (2, 1): {frozenset({(0, 4)})}, (1, 5): {frozenset({(1, 0)})}, (1, 1): {frozenset({(1, 4)})}}
>>> sampled = intvert.sample_2D(signal, known_coeffs)
>>> np.allclose(intvert.invert_2D(sampled, known_coeffs), signal)
True

Sampling with user selection and inverting with automatically selected coefficients:

>>> np.allclose(intvert.invert_2D(sampled), signal)
True

Inverting a larger example:

>>> np.random.seed(0)
>>> signal = np.random.randint(0, 2, (30, 20))
>>> sampled = intvert.sample_2D(signal)
>>> np.allclose(intvert.invert_2D(sampled), signal)
True

With insufficient precision, inversion may fail for long signals with large integers:

>>> signal = np.random.randint(0, 2, (29, 29))
>>> sampled = intvert.sample_2D(signal)
>>> try:
...         np.allclose(intvert.invert_2D(sampled), signal)
... except intvert.InversionError as err:
...         err
...
InversionError("Failure to recover a length 29 subproblem. It's possible that recovery was correct and the tolerance was too low. If you believer this is the case, try increasing epsilon. If recovery was incorrect, increasing precision and beta2 may aid in recovery.")

In this case, increasing precision and beta2 allows inversion:

>>> with gmpy2.get_context() as c:
...     c.precision = 100
...     sampled = intvert.sample_2D(signal)
...     np.allclose(intvert.invert_2D(sampled, beta2=1e16), signal)
...
True

Or providing more DFT coefficients also allows inversion:

>>> known_coeffs = intvert.select_coeffs_2D(29, 29, 2)
>>> sampled = intvert.sample_2D(signal, known_coeffs)
>>> np.allclose(intvert.invert_2D(sampled, known_coeffs), signal)
True