Practical Techniques for Generating Points and Visualizations¶

In this section we discuss some of the practical issues for constructing visualizations. These issues fall between “theory” and “implementation.”

The Set of Low-Rank Tensors¶

We define the set of tensors of separation rank at most $r$ by

$S_r=\left\{ T \,:\, T(i_1,i_2,\ldots,i_d) =\sum_{l=1}^r \prod_{k=1}^d V^l_k(i_k)\right\} \,.$

The set $S_r$ is not a subspace, but is star shaped. Thus $S_r$ is connected and simply connected, and the global geometric and topological properties are simple. In order to study more interesting geometric and topological properties of $S_r$ , we will consider tensors that are positive scalar multiples of one another to be equivalent, and then ask about the geometry and topology of this reduced set.

Initialization¶

A visualization may be initialized by one of

loading a saved visualization,
entering a few parameters and randomly generating a visualization consistent with them, or
entering precisely the slice to visualize.

In random entry mode, the initial parameters for the visualization are:

$d$ the dimension,
$M$ the resolution or a list $[M_1,M_2,\ldots,M_d]$ of direction-dependent resolutions,
$r$ the separation rank to visualize,
The field (real or complex) over which to work.
$r_b$ the separation rank of $T_1$ , $T_2$ , and (in the real case) $T_3$ .

With these parameters we can randomly generate $T_1$ , $T_2$ , and (in the real case) $T_3$ and start the visualization. To minimize distortions in the visualization, we normalize so $\|T_i\|=1$ .

In manual entry mode, the initial parameters for the visualization are:

$r$ the separation rank to visualize,
$T_1$ , $T_2$ , and (in the real case) $T_3$ , the tensors defining the slice.

The tensors $T_1$ , $T_2$ , and (in the real case) $T_3$ must have consistent dimension $d$ and resolutions $[M_1,M_2,\ldots,M_d]$ , but may have different ranks.

If $d$ , $M$ , $r$ , $T_1$ , $T_2$ , or $T_3$ change then we must start the visualization over.

Trimming Excess Points¶

Although we talk of plotting points, we actually plot small discs of some radius $R$ . As noted earlier, we plot dark discs over light discs since the dark ones are more interesting. We may then have the case where many light discs are used, but are covered by dark discs and thus invisible. They then serve only to slow down the software and so we wish to discard them. Determining if one disc is covered by a set of discs is a fairly hard computational problem, so we instead use an easy heuristic. We first sort all points by their angle from small to large and initialize an empty list of kept points. Looping through the points we check to see if the point is within $R/2$ of any point in the kept list. If it is then we discard this point and if it is not then we put it in the kept list.

We may also end up with points too distant from the $T_i$ , to be meaningful. In this case we discard points outside of a user-defined rectangle.

Easy to Generate Point and Lines¶

If the rank of $T_i$ is less than or equal to $r$ , then $T_i \in S_r$ and so it can be added to the visualization as a black point.

If the sum of the ranks of $T_i$ and $T_j$ is is less than or equal to $r$ , then all tensors on the line connecting $T_i$ and $T_j$ are in $S_{r}$ , and can be colored black in the visualization. In the real case the software then makes available the option to include the points on these lines. In the complex case this line is the entire visualization, so it is not interesting, but can be used for testing and debugging.

In the real case, if the sum of the ranks of $T_1$ , $T_2$ , and $T_3$ is is less than or equal to $r$ , then the entire plane should be black. This case is not interesting, but can be used for testing and debugging.

Generating Tensors of the Desired Separation Rank¶

The first strategy for generating points is to generate tensors in $S_r$ and plot them using the projection technique to determine the appropriate location and angle/color of the plotted point. The strength of this approach is that we can rapidly generate many points. The weakness of this approach is that many of these points are light colored and so not very meaningful.

One technique is to simply generate elements of $S_r$ randomly.

A second technique is to start with a tensor that is in $S_r$ and on the line/plane, and perform a random walk. Under the assumption that $r_b \le r$ , we can start with one of our $T_i$ . By randomly perturbing entries in its component vectors $V_k^l$ , we can generate a nearby point in $S_r$ . We could simply allow the random walk to continue, in which case we expect to drift away from the line/plane. Alternatively, we could reject moves that result in angles above some threshold and thereby restrict the walk to stay near the line/plane.

A third technique is to use a homotopy to smoothly morph one point in $S_r$ and on the line/plane to another such point. Calling the component vectors $V_k^l$ and $W_k^l$ , we can generate new component vectors $tV_k^l+(1-t)W_k^l$ for $0\le t\le 1$ (or a larger interval). The intermediate points are in $S_r$ and we can hope stay near the line/plane.

A fourth technique is to start with a tensor in $S_r$ but not on the line/plane, and do a random walk with descent. Any move that increases the angle is rejected

Note: These techniques have been tested but are not in the current software implementation.

Testing Tensors on the Line/Plane¶

The main alternative strategy is to generate tensors on the line/plane and then test them for membership in $S_r$ . As noted earlier this test is imperfect, and we also wish to include tensors in $S_r$ that are near the line/plane in the visualization. We use the following procedure:

The user defines a rectangular grid of tensors $V$ on the line/plane.
For each $V$ , a numerical algorithm is used to attempt to produce a $T\in S_r$ close to $V$ in that $\|T-V\|$ is small. We use the alternating least squares (ALS) fitting, in the version described in [BEY-MOH2005] .
The tensors $T\in S_r$ constructed above are included in the visualization.

When the ALS algorithm produces $T$ with $\|T-V\|$ very small then we can be confident that $V\in S_r$ (or is a limit of elements in $S_r$ ). However, if $\|T-V\|$ is large it may just indicate that the algorithm failed. False negatives may be identified when a light-colored point is surrounded by darker points. With repeated application, false negatives may also become covered by darker points.

ALS Performance Notes¶

The initial version of the ALS routine used here operates as follows.

A random $T\in S_r$ is generated.
A loop through all directions is performed, doing a linear least squares fitting in a single direction at a time. This loop is repeated until one of the following conditions is met:
- $\|T-V\|<10^{-3}$ ,
- the relative decrease in $\|T-V\|$ from doing a loop is less than $10^{-6}$ , or
- 50 iterations are performed.

On certain tests when it was know that the entire plotting plane was in $S_r$ , and thus we should get solid black, intead this routine achieved only yellow without even scattered black points (see A note on ALS failure). An improved version of the ALS routine was then implemented that operates as follows.

A random $T\in S_1$ is generated.
A loop from 1 to is performed in which
1. The ALS fitting loop through all directions is performed to improve $T$ , two times.
2. A random $T'\in S_1$ is generated and appended to $T$ .
A loop through all directions is performed, doing a linear least squares fitting in a single direction at a time. This loop is repeated until one of the following conditions is met:
- $\|T-V\|<10^{-3}$ ,
- the relative decrease in $\|T-V\|$ from doing a loop is less than $10^{-6}$ , or
- 50 iterations are performed.

In the test cases where the initial ALS failed to find black, the improved ALS succeeded in at least finding dark blue. It was notably slower than the original, perhaps indicating that the original was getting stuck in local minima and terminating early.

Coordinate Normalization¶

As noted earlier, in the real case $T_3$ is at $(0,0)$ and $T_1$ is in the direction $(1,0)$ at location $(\|T_1-T_3\|,0)$ . To ease the cognitive burden on the user, coordinates that the user enters are scaled so that $T_1$ corresponds to $(1,0)$ . Similarly, in the complex case we normalize so that $T_1$ corresponds to $1+0i$ .

Practical Techniques for Generating Points and Visualizations¶

The Set of Low-Rank Tensors¶

Initialization¶

Trimming Excess Points¶

Easy to Generate Point and Lines¶

Generating Tensors of the Desired Separation Rank¶

Testing Tensors on the Line/Plane¶

ALS Performance Notes¶

Coordinate Normalization¶

Table Of Contents

Previous topic

Next topic

This Page

Navigation

Practical Techniques for Generating Points and Visualizations¶

The Set of Low-Rank Tensors¶

Initialization¶

Trimming Excess Points¶

Easy to Generate Point and Lines¶

Generating Tensors of the Desired Separation Rank¶

Testing Tensors on the Line/Plane¶

ALS Performance Notes¶

Coordinate Normalization¶

Table Of Contents

Previous topic

Next topic

This Page

Quick search

Navigation