Skip to content

Should power_method_opnorm have provisions for unfortunate start values? #1685

@leftaroundabout

Description

@leftaroundabout

While stress-testing ODL (#1684), one of the problems I encountered is that power_method_opnorm occasionally gives a wrong result. Specifically, while it should give the highest singular value of a linear operator, sometimes the result is the lower singular value instead.

It is evident why this happens: if the (randomly chosen) starting point of the method lies very close to the second eigenvector of the operator, iterating it will always give back a very similar vector again, and never veer far into other parts of the operator's range.

Since this happens so rarely, it is perhaps acceptable. Changing the test to allow one out of three runs of the method to give a wrong result is enough to make it succeed essentially always (49166c0).

But it would also be easy to build something similar into power_method_opnorm itself: when not given an explicit start values, it could generate three randoms ones and use majority voting between them. This would of course be slower, but the typical use case is to run this only once at the start of an iterative scheme.

Alternatively, one could introduce stochasticity into the power-iterations - though then it should perhaps better be called simulated_annealing_opnorm.

Metadata

Metadata

Assignees

No one assigned

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions