corr_solver package

Submodules

corr_solver.corr_bspline_oracle module

Corr_bspline_oracle.py

This code is designed to work with B-splines, which are mathematical functions used to create smooth curves. The main purpose of this code is to generate a B-spline curve that fits a given set of data points while satisfying certain constraints, particularly a monotonic decreasing constraint.

The code takes several inputs, including data points (Y), the number of control points for the B-spline (site and m), an oracle function for optimization, and a core correlation function (corr_core). These inputs are used to create and optimize the B-spline curve.

The main output of this code is a B-spline object, which represents the fitted curve. It also returns the number of iterations taken to optimize the curve and a boolean indicating whether the optimization was successful (feasible).

To achieve its purpose, the code uses several functions and a class:

1. The mono_oracle function checks if a given sequence of numbers is monotonically decreasing (each number is less than or equal to the previous one). If it finds a violation, it returns information about where the violation occurred.

2. The mono_decreasing_oracle2 class wraps the mono_oracle function and provides an interface for the optimization process.

3. The corr_bspline function is the main function that ties everything together. It generates the B-spline information, sets up the optimization problem, and calls the core correlation function to optimize the B-spline coefficients.

4. The generate_bspline_info function creates the necessary information for constructing a B-spline, including the knot vector (t) and the basis functions (Sigma).

The code follows this general flow:

1. Generate the B-spline information (knots, basis functions)

2. Set up the optimization problem with constraints

3. Optimize the B-spline coefficients

4. Create and return the final B-spline object

An important part of the logic is the monotonic decreasing constraint, which ensures that the resulting B-spline curve always decreases (or stays flat) as it moves from left to right. This is enforced through the mono_oracle and mono_decreasing_oracle2 functions.

The code also performs some data transformations, such as converting the input site points into a distance matrix, and creating B-spline basis functions. These transformations help in setting up the optimization problem and constructing the final B-spline curve.

Overall, this code provides a way to fit a smooth, monotonically decreasing curve to a set of data points, which can be useful in various applications such as data analysis, signal processing, or computer graphics.

corr_solver.corr_bspline_oracle.corr_bspline(Y, site, m, oracle, corr_core)

The corr_bspline function takes in input parameters Y, site, m, oracle, and corr_core, and returns a BSpline object, the number of iterations, and a feasibility indicator.

Parameters:

• Y – The input data Y for the B-spline algorithm

• site – The parameter site represents the number of control points in the B-spline curve. It determines the flexibility and smoothness of the curve

• m – The parameter m represents the number of control points in the B-spline curve. It determines the flexibility and smoothness of the curve. A higher value of m will result in a more flexible curve that can better fit the data, but it may also lead to overfitting

• oracle – The oracle parameter is a separation oracle

• corr_core – The corr_core parameter is a function that takes in the following arguments:

Returns:

The function corr_bspline returns three values:

corr_solver.corr_bspline_oracle.generate_bspline_info(site, m)

The function generate_bspline_info generates B-spline information given a set of points and a desired number of B-splines.

Parameters:

• site – The parameter site is a list or array of data points that define the shape or curve that you want to approximate using B-splines

• m – The parameter m represents the number of B-spline basis functions to generate. It determines the number of basis functions that will be used to approximate the input data

Returns:

The function generate_bspline_info returns three values: Sigma, t, and k.

class corr_solver.corr_bspline_oracle.mono_decreasing_oracle2(basis)

Bases: object

Oracle for monotonic decreasing constraint.

Wraps a basis oracle and enforces that the sequence of B-spline coefficients must be monotonically non-increasing (non-increasing x[i] >= x[i+1]).

assess_optim(x: ndarray, t: float) → Tuple[Tuple[ndarray, float], float | None]

The function assess_optim assesses the optimality of a given solution by checking if it satisfies a monotonic decreasing constraint, and if not, it calls another function to assess optimality.

Parameters:

• x (Arr) – An array of values

• t (float) – The parameter t represents the best-so-far optimal value. It is a float value that is used in the function to assess the optimality of a solution

Returns:

The function assess_optim returns a tuple containing a Cut object and an optional float value.

corr_solver.corr_bspline_oracle.mono_oracle(x)

The mono_oracle function is an oracle that checks if a given array x satisfies the monotonic decreasing constraint and returns the gradient and the first violation if it exists.

Parameters:

x – The parameter x is a list or array of numbers. It represents a sequence of values that we want to check for the monotonic decreasing constraint

Returns:

The function mono_oracle returns two values: g and fj. g is a numpy array of zeros with the same length as x, where elements are set to -1.0 and 1.0 to enforce the monotonic decreasing constraint. fj is the difference between the next element and the current element in x.

corr_solver.corr_oracle module

Correlation Oracle (corr_oracle.py)

This code is a collection of functions that work together to analyze and model relationships between data points in a two-dimensional space. It’s designed to help understand patterns and correlations in data, particularly for spatial data analysis.

The main purpose of this code is to create and manipulate data representing locations (called “sites”) in a 2D space, generate correlation matrices based on these locations, and then fit a polynomial model to describe the relationships between these points.

The code takes various inputs depending on the function being used. These inputs include the number of sites to generate, the locations of sites, and parameters for controlling the complexity of the models being created.

The outputs produced by this code include:

1. Arrays of site locations

2. Correlation matrices

3. Distance matrices

4. Polynomial models that describe the relationships between data points

The code achieves its purpose through several steps:

1. It starts by creating a set of 2D sites using a special sequence called the Halton sequence. This helps distribute the points evenly across the space.

2. Then, it generates a correlation matrix for these sites. This matrix represents how closely related each pair of sites is to each other based on their distances.

3. The code also constructs distance matrices, which simply contain the distances between each pair of sites.

4. Using these distance matrices, it builds more complex matrices that represent polynomial relationships between the sites.

5. Finally, it uses all of this information to fit a polynomial model that best describes the relationships between the data points.

Some important transformations happening in the code include:

• Converting site locations into distance and correlation matrices

• Using matrix operations to generate correlated random data

• Building polynomial matrices of increasing degrees

The code uses mathematical concepts like covariance matrices, Cholesky decomposition, and polynomial fitting. However, at its core, it’s about taking spatial data, analyzing the relationships between points, and creating a model that can describe these relationships.

This tool could be useful in fields like geography, environmental science, or any area where understanding spatial relationships is important. It provides a way to take raw location data and turn it into a mathematical model that can help predict or explain patterns in the data.

corr_solver.corr_oracle.construct_distance_matrix(site: ndarray) → ndarray

The function construct_distance_matrix takes in a list of site locations and returns a distance matrix object where each element represents the distance between two sites.

Parameters:

site (Arr) – The parameter site is the location of sites. It is an array that contains the coordinates of each site

Returns:

a distance matrix object.

corr_solver.corr_oracle.construct_poly_matrix(site: ndarray, m) → List[ndarray]

The function construct_poly_matrix takes in a list of site locations site and a degree m, and returns a list of distance matrices for a polynomial of degree m.

Parameters:

• site (Arr) – The parameter site is the location of sites, which is expected to be an array. It represents the locations of the sites for which the distance matrix is being constructed

• m – The parameter m represents the degree of the polynomial. It determines the number of distance matrices that will be constructed

Returns:

The function construct_poly_matrix returns a list of arrays.

corr_solver.corr_oracle.corr_poly(Y, site, m, oracle, corr_core)

The function corr_poly takes in a signal Y, a sparsity level site, a maximum degree m, an oracle function, and a correction core function, and returns a polynomial, the number of iterations, and a feasibility indicator.

Parameters:

• Y – The parameter Y represents the input data, which is a vector or matrix of shape (n_samples, n_features). It contains the input variables for which we want to find a polynomial correlation

• site – The parameter site represents the degree of the polynomial. It determines the number of coefficients in the polynomial

• m – The parameter m represents the degree of the polynomial that you want to construct. It determines the number of coefficients in the polynomial

• oracle – The oracle parameter is a function that takes in two arguments: Sigma and Y. Sigma is a matrix and Y is a vector. The oracle function returns a vector omega

• corr_core – The corr_core parameter is a function that takes in the following arguments:

Returns:

The function corr_poly returns a tuple containing three elements: 1. A polynomial object representing the polynomial fit to the data. 2. The number of iterations performed during the correction process. 3. A boolean value indicating whether a feasible solution was found.

corr_solver.corr_oracle.create_2d_isotropic(site: ndarray, N=3000) → ndarray

The function create_2d_isotropic generates a biased covariance matrix for a 2D isotropic object based on the location of sites.

Parameters:

• site (Arr) – The parameter site is the location of sites. It is expected to be a 2D array where each row represents the coordinates of a site

• N – The parameter N represents the number of iterations or samples used to create the 2D isotropic object. It determines the number of times the loop runs to generate random values and calculate the outer product. The larger the value of N, the more accurate the estimation of the biased covariance matrix will be,, defaults to 3000 (optional)

Returns:

The function create_2d_isotropic returns a biased covariance matrix Y.

corr_solver.corr_oracle.create_2d_sites(nx=10, ny=8) → ndarray

The function create_2d_sites generates a 2D array of site locations using the Halton sequence.

Parameters:

• nx – The parameter nx represents the number of sites in the x-direction, while ny represents the number of sites in the y-direction, defaults to 10 (optional)

• ny – The parameter ny represents the number of rows in the 2D sites object, defaults to 8 (optional)

Returns:

The function create_2d_sites returns a 2D array representing the location of sites.

corr_solver.gmi_oracle module

class corr_solver.gmi_oracle.GMIOracle(H, m)

Bases: object

Oracle for General Matrix Inequality constraint

H(x) >= 0

H.eval(row, col, x): function evalution at (row, col)-element H.neggrad[k](rng, x): negative gradient in range rng, the k-term

assess_feas(x: ndarray) → Tuple[ndarray, float] | None

The assess_feas function assesses the feasibility of a given input x and returns a cut if it is infeasible, otherwise it returns None.

Parameters:

x (np.ndarray) – An input array of type np.ndarray

Returns:

The function assess_feas returns an optional Cut object.

corr_solver.lsq_corr_oracle module

Least Squares Correlation Oracle

This code defines a class called lsq_oracle (least squares oracle) that is designed to solve a specific type of optimization problem. The purpose of this code is to find the best solution to a mathematical problem involving matrices and inequalities.

The lsq_oracle class takes two inputs when it’s created: a list of arrays called F and another array called F0. These inputs represent mathematical objects that define the problem the oracle is trying to solve.

The main output of this code is produced by the assess_optim method. This method takes two inputs: an array x (which represents a potential solution) and a float t (which represents the best solution found so far). It returns information about whether the given solution is feasible and optimal, and if not, it provides guidance on how to improve the solution.

The code achieves its purpose through a two-step process:

1. First, it checks if the solution satisfies certain constraints using the lmi0 oracle. 2. If that passes, it then checks another set of constraints using the qmi oracle.

If either of these checks fail, the method returns information about how the solution violates the constraints. If both checks pass, it compares the current solution to the best solution found so far.

An important transformation happening in this code is the conversion of the original problem into a slightly different form. Instead of directly minimizing the difference between F0 and F(x), it introduces a new variable t and tries to minimize t while ensuring that certain conditions involving t are met. This transformation allows the problem to be solved using standard optimization techniques.

The code uses some advanced mathematical concepts (like matrix inequalities) that might be challenging for a beginner to fully understand. However, the overall structure of the code follows a logical flow: initialize the problem, check constraints, and either return information about constraint violations or assess the optimality of the solution.

In simple terms, you can think of this code as a smart calculator that’s trying to solve a complex math problem. It takes in the problem description (F and F0), tries different solutions (x), and tells you whether each solution is good or not, and how to make it better if it’s not good enough.

class corr_solver.lsq_corr_oracle.lsq_oracle(F: List[ndarray], F0: ndarray)

Bases: object

Oracle for least-squares estimation.

Solves the problem: min ||F0 - F(x)|| s.t. F(x) >= 0

The oracle transforms the problem into:

min t s.t. x[n+1] <= t

x[n+1]*I - F(x)^T F(x) >= 0

where F(x) = F[1] x[1] + … + F[n] x[n] and {Fk}i,j = Ψk(||sj - si||)

assess_optim(x: ndarray, t: float) → Tuple[Tuple[ndarray, float], float | None]

The assess_optim function assesses the optimality of a given solution x and returns a tuple containing a cut and an optional float value.

Parameters:

• x (Arr) – The parameter x is of type Arr, which is likely a numpy array or a list of numbers. It represents some input values for the optimization problem

• t (float) – The parameter t represents the best-so-far optimal value. It is a float value that is used in the assessment of the optimization problem

Returns:

The function assess_optim returns a tuple containing two elements. The first element is a tuple (g, fj) which represents a cut and its corresponding objective value. The second element is an optional float value tc if fj > 0.0, otherwise it is None.

corr_solver.mle_corr_oracle module

mle_oracle

This code defines a class called mle_oracle which is designed to solve a maximum likelihood estimation problem. The purpose of this code is to find the best parameters for a statistical model based on observed data, while satisfying certain constraints.

The mle_oracle class takes two inputs when initialized: Sigma and Y. Sigma represents a covariance matrix, which describes how different variables in a dataset are related to each other. Y is a biased sample covariance matrix, which is an estimate of the true covariance based on observed data.

The main output of this class is produced by the assess_optim method. This method takes two inputs: x (a set of coefficients) and t (the best optimal value found so far). It returns a tuple containing information about whether the current solution is feasible and optimal, along with some additional values used in the optimization process.

To achieve its purpose, the code uses a technique called linear matrix inequality (LMI) optimization. It creates two LMI oracles (lmi0 and lmi) which are used to check if the current solution satisfies certain constraints. The assess_optim method first checks if the solution is feasible using these oracles. If it’s not feasible, it returns information about why it’s not feasible.

If the solution is feasible, the method then calculates a value f1, which represents the objective function of the maximum likelihood estimation problem. This calculation involves matrix operations like inversion, multiplication, and calculating traces and determinants. The method also computes a gradient g, which indicates how the objective function changes with respect to small changes in the input x.

Finally, the method compares the calculated f1 with the input t to determine if a better solution has been found. If f1 is better than t, it returns this new value along with the gradient. Otherwise, it returns information that can be used to continue the optimization process.

The important logic flows in this code include the feasibility checks, the calculation of the objective function and its gradient, and the comparison of the current solution with the best known solution. The data transformations mainly involve matrix operations on the input covariance matrices.

Overall, this code provides a way to solve a complex statistical optimization problem by iteratively improving a solution while ensuring it satisfies certain constraints. It’s a building block that would typically be used as part of a larger optimization algorithm.

class corr_solver.mle_corr_oracle.mle_oracle(Sigma: List[ndarray], Y: ndarray)

Bases: object

assess_optim(x: ndarray, t: float) → Tuple[Tuple[ndarray, float], float | None]

The assess_optim function assesses the feasibility and optimality of a given solution by calculating various values and returning a tuple of cuts and a float value.

Parameters:

• x (Arr) – The parameter x is a numpy array representing the coefficients of basis functions. It is used as input to assess the feasibility of a solution

• t (float) – The parameter t represents the best-so-far optimal value. It is a float value that is used in the calculation of the objective function f

Returns:

The function assess_optim returns a tuple containing two elements. The first element is a Cut object or a tuple (g, f) depending on the condition. The second element is either None or a float value.

corr_solver.qmi_oracle module

class corr_solver.qmi_oracle.QMIOracle(F, F0)

Bases: object

class QMI(F: List[ndarray], F0: ndarray)

Bases: object

Oracle for Quadratic Matrix Inequality

The QMI class represents an oracle for solving a quadratic matrix inequality problem.

find x s.t. t*I - F(x)’ F(x) ⪰ 0

where

F(x) = F0 - (F1 * x1 + F2 * x2 + …)

count = 0

eval(row, col, x: ndarray) → float

The eval function calculates a value based on the given parameters and returns it.

Parameters:

• row – The parameter row represents the row index of the element in the matrix

• col – The parameter col represents the column index of the element in the matrix

• x (Arr) – The parameter x is an array

Returns:

a float value.

neg_grad_sym_quad(Q, _: ndarray)

The function neg_grad_sym_quad calculates the negative gradient of a symmetric quadratic function.

Parameters:

• Q – Q is a quadratic matrix represented as a sparse matrix. It has two attributes: p and v. p is a tuple representing the starting and ending indices of the non-zero elements in the matrix, and v is a numpy array representing the values of the non-zero elements

• _ (Arr) – The parameter _ is an unused placeholder parameter

Returns:

the gradient vector g.

t = 0.0

update(t: float)

The update function updates the value of self.t with the input t.

Parameters:

t (float) – The parameter t represents the best-so-far optimal value

assess_feas(x: ndarray) → Tuple[ndarray, float] | None

The assess_feas function assesses the feasibility of a given input and returns a cut if it is feasible.

Parameters:

x (Arr) – An array of values

Returns:

an Optional[Cut] object.

update(t: float)

The function updates the best-so-far optimal value.

Parameters:

t (float) – The parameter t represents the best-so-far optimal value

Module contents