Abstract Summary
A class of underdetermined problems that has received much attention is that where the sparsest solution is assumed to be the most likely. A brute force search for this solution is conceptually straightforward but, except for small problems, computationally prohibitive. Surrogates that allow for efficient solutions include greedy algorithms that look for sparseness in the vicinity of some initial starting point, such as the Iterative Hard Thresholding, the Matching Pursuit or the Orthogonal Matching Pursuit, as well as schemes that relax mini-mum cardinality for solutions with minimum L1 norm. Solution selection based on minimum L1 norm is known to promote sparseness and these solutions can, in the linear case, be extracted efficiently using linear programming. The model updating problem in structural mechanics is nonlinear and the question that arises is whether the performance of linear (sparsity-promoting) techniques may be significantly affected by the deviations from linearity. For small parameter changes one expects that nonlinearity can be appropriately accommodated by denoising, i.e. by relaxing the equality constraints to constraints on the maximum norm of residuals, but small parameter changes are difficult to characterize due to noise and model error so the practical question pertains to parameter changes that are substantial. This paper examines a recently introduced approach known as the Quadratic Basis Pursuit (QBP) that attempts to extend Basis Pursuit (BP) to quadratic nonlinearities and which can be efficiently solved using semi-definite programming. It is found that in contrast with BP the QBP algorithm does not guarantee extraction of the vector with minimum L1 norm from the feasible vector space and is thus, at least in this sense, is not a literal extension of BP to quadratic nonlinearities. The foregoing is shown to be a consequence of the fact that the ordering of any vector space by increasing L1 norm does not generally coincide with the ordering that is realized when this criterion is applied to the rank one matrices formed from these vectors by the lifting operator, which is the way the vectors are represented in the QBP algorithm. A Monte Carlo simulation study using vectors with entries generated from a Gaussian distribution showed that the probability that the vector with the lowest L1 norm maps to the lifted matrix with the lowest L1 is around 40% for vectors with 20 entries and only around 25% when the dimension grows to 60. Reproduction of some previously published results shows that performance claims are limited to the specific conditions considered and can be drastically modified by changes in items that were not in the discussion, for example, changes in the magnitude of the entries of the solution vector. Albeit preliminary, the central observation from this work is that the performance of the QBP in its present form in the updating of underdetermined problems in mechanics is poor.
