# Perron-Frobenius matrix completion¶

The DGP atom library has several functions of positive matrices, including the trace, (matrix) product, sum, Perron-Frobenius eigenvalue, and $$(I - X)^{-1}$$ (eye-minus-inverse). In this notebook, we use some of these atoms to formulate and solve an interesting matrix completion problem.

In this problem, we are given some entries of an elementwise positive matrix $$A$$, and the goal is to choose the missing entries so as to minimize the Perron-Frobenius eigenvalue or spectral radius. Letting $$\Omega$$ denote the set of indices $$(i, j)$$ for which $$A_{ij}$$ is known, the optimization problem is

$\begin{split}$$\begin{array}{ll} \mbox{minimize} & \lambda_{\text{pf}}(X) \\ \mbox{subject to} & \prod_{(i, j) \not\in \Omega} X_{ij} = 1 \\ & X_{ij} = A_{ij}, \, (i, j) \in \Omega, \end{array}$$\end{split}$

which is a log-log convex program. Below is an implementation of this problem, with specific problem data

$\begin{split}A = \begin{bmatrix} 1.0 & ? & 1.9 \\ ? & 0.8 & ? \\ 3.2 & 5.9& ? \end{bmatrix},\end{split}$

where the question marks denote the missing entries.

import cvxpy as cp

n = 3
known_value_indices = tuple(zip(*[[0, 0], [0, 2], [1, 1], [2, 0], [2, 1]]))
known_values = [1.0, 1.9, 0.8, 3.2, 5.9]
X = cp.Variable((n, n), pos=True)
objective_fn = cp.pf_eigenvalue(X)
constraints = [
X[known_value_indices] == known_values,
X[0, 1] * X[1, 0] * X[1, 2] * X[2, 2] == 1.0,
]
problem = cp.Problem(cp.Minimize(objective_fn), constraints)
problem.solve(gp=True)
print("Optimal value: ", problem.value)
print("X:\n", X.value)

Optimal value:  4.702374203221372
X:
[[1.         4.63616907 1.9       ]
[0.49991744 0.8        0.37774148]
[3.2        5.9        1.14221476]]
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 1, "mathjax_display_tex": 1, "mathjax_asciimath": 1, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 1, "x-ck12": 0, "texerror": 0, "math_score": 0.9947342276573181, "perplexity": 1972.240655099793}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "warc_path": "s3://commoncrawl/crawl-data/CC-MAIN-2022-05/segments/1642320303356.40/warc/CC-MAIN-20220121101528-20220121131528-00226.warc.gz"}