Short of a common enemy (i.e. Mongols/Huns/Caliphate) I can't see this happening without an outright conquest of one by the other - and I'd put my money on the Romans.
A PoD I think COULD work (Not will, it'll probably require some more research) would be an Emperor going Julius Caesar on Arabia, and trying to earn money from taxing the area, and Indian ocean trade. That should (hopefully) eliminate a Caliphate if they don't burn everything to the ground (and if a certain prophet stays/dies in Aksum).
If they can win over the Bedouin tribes as allies to raid Mesopotamia to weaken the Persians, it would open them up for invasion, and if they have a seafaring presence, they may be able to harass any persian merchant traffic.
By the end of it however, you have an even larger - and more precarious empire at the end. You may even need to move the capital from Constantinople to Damascus (or better location) - or have an incredibly powerful collection of governors.
It would mean that this new Alexander-Style Empire could have elephants - and seeing Elephant-Cataphrats would be epic