The Cambridge Grammar of the English Language (Page 1266-67) has this section:
10 Verbless clauses
We confine our attention here to verbless clauses in dependent or supplement functions comparable to those realised by non-finite clauses, as described in the main part of the chapter.
(a) Complement to with and without
 i They were standing against the wall [with their hands above their heads].
ii They were wandering around [without any clothes on].
The [boldfaced] clauses have subject + predicate structure, but with no verb in the predicate. With and without do not license finite complements, but non-finites are found in addition to the verbless forms (see §8.3 above).
With is semantically similar to have, and without to not have: [i–ii], for example, entail They had their hands above their heads, They didn’t have any clothes on.
CGEL is saying the boldfaced portions after with/without are verbless clauses. In [i], their hands is the subject, and above their hands the predicate. In [ii], any clothes is the subject, and on the predicate.
As suggested by CGEL, with/without can be replaced with having/not having as follows:
(1) They were standing against the wall [having their hands above their heads].
(2) They were wandering around [not having any clothes on].
Here, can you say that having and not having take verbless clauses as complements?
Are their hands above their heads and any clothes on verbless clauses?
If not, why do you consider the same construction as verbless clauses when they're complements to with/without?